Shortest Path

JointJS+ provides a shortestPath plugin that enables the ability to return an array of IDs of nodes on the shortest path between source and target.

Installation

Access shortestPath via the graphUtils namespace.

import { graphUtils } from '@joint/plus';

graphUtils.shortestPath(graph, source, target);

There is also a UMD version available

Include joint.graphUtils.js, joint.alg.priorityQueue.js and joint.alg.dijkstra.js in your HTML:

index.html

<script src="joint.js"></script>
<script src="joint.alg.priorityQueue.js"></script>
<script src="joint.alg.dijkstra.js"></script>
<script src="joint.graphUtils.js"></script>

Access shortestPath through the joint.graphUtils namespace:

index.js

joint.graphUtils.shortestPath(graph, source, target);

How does shortestPath work?

Return an array of IDs of nodes on the shortest path between source and target. source and target can either be elements or IDs of elements. opt.weight is an optional function returning a distance between two nodes. It defaults to function(u, v) { return 1 }. If opt.directed is true, the algorithm will take link direction into account. The implementation uses the alg.Dijkstra plugin internally. Please refer to the plugin documentation for more information.

Direct usage of Dijkstra

joint.alg.Dijkstra is a function that takes a graph represented as an adjacency list, a source node and optionally a weight function. The adjacency list is an object where a key is a node ID and value is an array or IDs of the neighbouring nodes of that node. If you want to use alg.Dijkstra directly on a JointJS graph, you first have to convert the graph into the adjacency list. (This is what the shortestPath() method from the alg.GraphUtils plugin does for you internally.) weight function is a function that takes two nodes and returns a distance between them. How you define distance between two nodes is completely on you. By default, the distance is always 1. Only keep in mind that the Dijkstra's algorithm requires the weight to be a positive integer.

The function returns a special object that encodes the shortest paths between the node provided and all the other nodes in the graph.

const graph = {
    a: ['b', 'c'],
    b: ['d', 'e'],
    c: ['f', 'g'],
    f: ['b'],
    e: ['c'],
    h: ['f', 'g'],
    i: ['h', 'a', 'd', 'g'],
    j: ['a']
};

const previous = joint.alg.Dijkstra(graph, 'a');
// { b: "a", c: "a", e: "b", f: "c" }