Part of course:

Dijkstra's algorithm (Shortest path algorithm)

- Video with Step-by-Step Example
- Algorithm steps
- Pseudo-code
- Why does the algorithm work?
- Run-time analysis
- Further reading

NaN.

Dijkstra's algorithm (Shortest path algorithm)[ Edit ]

Dijkstra's algorithm is an efficient single-source shortest path algorithm. As opposed to breadth-first search, it efficiently solves the single-source shortest path problem for **weighted graphs** (graph with weighted edges). For the algorithm to work, **all edge weights must be positive** (0 is allowed).

This video describes the problem statement and shows what the Dijkstra's algorithm does step-by-step on a well chosen example.

Given a graph and source, Dijkstra's algorithm calculates the distance of the shortest path from source to every node in the graph. The algorithm steps are as follows :-

- Mark all nodes as unvisited.
- Assign every node a
*tentative*distance. distance(source) = 0. distance(node) = infinity for all the nodes. - Set the source as the
*current node*. - Mark
*current node*as visited. (This ensures**each node is visited exactly once**). - Consider all
*unvisited neighbors*of the*current node*: - Calculate a new
*tentative*distance for the neighbor for the path through the current node. tentative_distance = distance(current node) + edge_weight(current node, neighbor) - If the newly calculated distance is better (smaller) than the current value of distance(neighbor), update distance(neighbor).
- Set
*current node*=*unvisited node with the smallest tentative distance*. This node's*tentative*distance**is now final and known for sure**. Repeat from step 4. If there are no more unvisited nodes, or distance for all*unvisited*nodes = infinity (happens for disconnected graphs), then stop.

define dijkstra(graph, source):# initializationdistance[node] = INFINITY for all nodes in graphprevious[node] = UNKNOWN for all nodes in graphvisited[node] = False for all nodes in graphheap = empty heap# start from sourcedistance[source] = 0heap.insert_with_priority(distance[source], source)while not heap.empty(): # at-least one unvisited node# unvisited vertex with minimum distancenode = heap.pop()if visited[node]: continuevisited[node] = True # mark visitedfor each unvisited neighbor of node:# calculate distance of new pathnew_distance = distance[node] + edge_weight(node, neighbor)# check if we found a better path than current bestif distance[neighbor] is None or new_distance < distance[neighbor]:# if yes, update distance[] and previous[]distance[neighbor] = new_distanceprevious[neighbor] = nodeheap.insert_with_priority(distance[neighbor], neighbor)return distance, previous

The main invariant that Dijkstra's algorithm maintains is the following: At the beginning of each iteration, for all *visited* nodes distance(node) is the optimal shortest-path distance. For all *unvisited* nodes, distance(node) is the shortest-path distance *via visited nodes only*.

We can prove this by induction.

Initially, this is true when we mark the source as visited and finish iterating over its neighbors.

Now, the *unvisited* node with the smallest distance must also have the correct shortest distance. (why? hint: use invariant above; this also assumes graph weights are positive). So when we choose this node and mark it *visited*, the first half of the invariant (regarding *visited* nodes) is still true. Right after this, we calculate *tentative* distances for all it's neighbors and update them if we find a better distance. Hence, the second half of the invariant (regarding *unvisited* nodes) is also true.

For a graph with n nodes and m edges, the runtime of Dijkstra's algorithm is O(m \log n) - assuming we use heaps to find the "unvisited vertex with minimum distance".

This is because each node gets visited exactly once, and each edge is relaxed exactly once. Hence, we insert into the heap m times (once per edge), which takes O(\log n) time per operation.

All other operations (apart from heap insert and pop) take O(m) time total, since we perform O(1) work per edge. This is dominated by the time taken by the heap operations.

Read more…(499 words)

Mark as completed

Previous

[Hackerrank] Journey to the moon

Next

[SHPATH] The Shortest Path

Part of courses:

About the contributor:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Dijkstra's algorithm (Shortest path algorithm)

- Video with Step-by-Step Example
- Algorithm steps
- Pseudo-code
- Why does the algorithm work?
- Run-time analysis
- Further reading

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.