Dijkstra's Algorithm

Dijkstra's Algorithm is used to find the shortest path between nodes in a graph.

Features about Dijkstra's algorithm

• Solves the problem of finding the shortest path.
• Finds the shortest (lowest cost) path in a graph from start node to end node.
• Fastest, single start, shortest path in a graph with non-negative edges.

Complexity of Dijkstra's algorithm

1. Maximum number of paths in priority queue: O(E)
2. Adding/removing a path from the priority queue: O(logE)

Wikipedia - for more information.

dijkstra(v):
pq = new PriorityQueue()
pq.insert([dest:v, pred:null, cost:0])
while(!pq.isEmpty()):
[dest, pred, cost] = pq.removeMin()
if dest is unvisited:
mark dest as visited, store pred and cost for dest
for each edge with weight w to unvisited neighbor u of dest:
pq.insert([u, dest, cost+w])