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.
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>
Even though alg.Dijkstra
is listed as a separate plugin, you usually don't
use it directly. Instead, you can use the dia.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.
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; }


alg.PriorityQueue
is an implementation of the Priority Queue abstract data type.
It is like a normal stack or queue, but where each item has assigned a priority (a number). Items with
higher priority are served before items with lower priority. This implementation uses binary heap as
an internal representation of the queue. The time complexity of all the methods is as follows:
create
: O(n)
insert
: O(log n)
peek
: O(1)
peekPriority
: O(1)
remove
: O(log n)
isEmpty
: O(1)
alg.PriorityQueue
is used internally by the alg.Dijkstra algorithm for finding the
shortest path in a graph. It is however useful on its own, that's why it is listed as a separate plugin.
Include joint.alg.priorityQueue.js
file into your HTML:
<script src="joint.alg.priorityQueue.js"></script>
The usage of alg.PriorityQueue
is pretty simple. You just have to create
an object of the joint.alg.PriorityQueue
type. Then you can insert, remove or
retrieve elements from the queue similarly as you would do with a normal JavaScript array.
var q = new joint.alg.PriorityQueue;
q.insert(1, 'one');
q.insert(3, 'three');
q.insert(2, 'two');
q.peek() // the first value is 'one'
q.peekPriority() // the first priority is 1
q.remove() // the first value was 'one'
q.remove() // the second value was 'two'
q.remove() // the third value was 'three'
q.isEmpty() // true
Moreover, this implementation of the priority queue allows you to update priorities
of any item that you have inserted into the queue. This is also known as the
operation. For this to work, you have to
give each item you insert into the queue a unique ID. This is because in
JavaScript, objects do not have unique IDs by default. Therefore, there
is no way the decreaseKey
alg.PriorityQueue
can know which item you'd like to
update priority for. Here is an example of priority queue that uses the
updatePriority()
operation:
var q = new joint.alg.PriorityQueue;
q.insert(1, 'one', 'id1');
q.insert(3, 'three', 'id3');
q.insert(2, 'two', 'id2');
q.peek() // the first value is 'one'
q.updatePriority('id1', 5);
q.peek() // now the first value is 'two'
q.updatePriority('id1', 1);
q.peek() // the first value 'one' got again back to the top
joint.alg.PriorityQueue([opt])  Create a priority queue object. If opt.data array is passed,
it must be an array of items of the form { priority: Number, value: Object } .
In this case, the priority queue will be initialized with this array. It's like
calling insert(priority, value) for each item of this array.
opt.comparator can optionally be a function that will be used
to compare two priorities. The signature of this function is function(a, b) .
The function should return a value less then 0 if priority a is lower
than priority b , value equal to 0 if the priorities are the same
and value bigger than 0 if priority a is higher than priority b .
The comparator function defaults to: function(a, b) { return a  b } .
This function effectively allows you to use any object as a priority in which case
it is on you to tell the priority queue how to compare two priorities.


isEmpty()  Return true if the priority queue is empty, false otherwise.

insert(priority, value [, id])  Insert a value with priority to the queue. Optionally
pass a unique id of this item. Passing unique IDs for each item
you insert allows you to use the updatePriority() operation.
See the Usage section for details.

peek()  Return the value of an item with the highest priority. 
peekPriority()  Return the highest priority in the queue. 
remove()  Return the value of an item with the highest priority and remove the item from the queue. 
updatePriority(id, priority)  Update priority of an item identified by a unique id . You can
only use this operation if all the items you inserted to the queue had a unique
ID assigned. See the Usage section for details.
