ðŸŽ‰ JointJS has new documentation! ðŸ¥³

# JointJS+ Dijkstra

### alg.Dijkstra

`alg.Dijkstra` is an implementation of the Dijkstra's shortest path algorithm. It can efficiently find the shortest path in both directed and undirected graphs. This implementation uses a binary heap based priority queue. The time complexity of this algorithm is `O(|E| + |V| log |V|)`, where `|E|` is the number of edges in the graph and `|V|` is the number of nodes.

### Install

Include both `joint.alg.dijkstra.js` and its priority queue dependency files into your HTML:

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

### Usage

Even though `alg.Dijkstra` is listed as a separate plugin, you usually don't use it directly. Instead, you can use the `graphUtils` plugin which extends the `joint.dia.Graph` with a convenience method for finding the shortest path between two nodes `shortestPath(source, target [, opt])`. However, it could be useful to use `alg.Dijkstra` directly in some situations. The reason is that `alg.Dijkstra` calculates not only the shortest path between two nodes but the shortest path between a node and all the other nodes in the graph.

`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.

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

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

The above example shows the result of the `joint.alg.Dijkstra` function. This special object allows us to get the shortest path to all the nodes in the graph starting at node `'a'`. For example, the shortest path to the node `'f'` is a path `['a', 'c', 'f']`. How did we get there? You simply start from your target node and keep asking the returned object node by node till you reach your source node. In other words, we start by `previous['f']` which gives us `'c'` Then we ask for `previous['c']` which gives us `'a'` and we're done since we reached our source node.

### API

joint.alg.Dijkstra(adjacencyList, source [, weight]) Find the shortest path between the node `source` and all the other nodes in the graph represented as `adjacencyList`. See the Usage section for more info. `weight` can optionally contain a function that takes two nodes and returns the distance between them. This function defaults to: `function(u, v) { return 1; }`