Introduction
Create a graph
Run the algorithm
Description of the algorithm
Exercise 1
Exercise 2
Exercise 3
More

What's the cheapest way from left to right?

The classic among shortest path algorithms

You want to know, how to get from Munich to Cologne as fast as possible? Is the fastest route via Stuttgart or via Frankfurt? Dijkstra's Algorithm can help you! With this algorithm, you can find the shortest path in a graph. The vertices of the graph can, for instance, be the cities and the edges can carry the distances between them.

Dijkstra's Algorithm can also compute the shortest distances between one city and all other cities. And the edges can describe costs, distances, or some other measure that is helpful for the user.

An important restriction of Dijkstra's Algorithm is, that all edge costs (which is how we call the edge labels) must not be negative.

This applet presents Dijkstra's Algorithm, which calculates shortest paths in graphs with positive edge costs.

What do you want to do first?

SVG Download

Legend

	Node
	Edge with weight 50

Legend

Which graph do you want to execute the algorithm on?

Start with an example graph:

Modify it to your desire:

To create a node, make a double-click in the drawing area.
To create an edge, first click on the output node and then click on the destination node.
The edge weight is changed with a double-click on the edge.
Right-clicking deletes edges and nodes.

Download the modified graph:

Download

Upload an existing graph:

occured when reading from file:

the contents:

What next?

SVG Download

Legende

	Starting node from where distances and shortest paths are computed.
	Node being processed.
	Node in the priority queue.
	"Predecessor edge" that is used by the shortest path to the node.

Legend

Algorithm status

rewind fast forward

Explanation
Pseudocode

BEGIN

d(v[1]) ← 0

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

WHILE queue ≠ ∅ DO

u = queue.extractMin()

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, parent(w) = (u,w)

ELSE IF parent(w) == NULL THEN

d(w) = dist, parent(w) = (u,w)

queue.insert(w,dist)

END

Priority Queue:

Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

What's the shortest path from left to right?

Shortest Paths

In many applications one wants to obtain the shortest path from a to b. Depending on the context, the length of the path does not necessarily have to be the length in meter: One can as well look at the cost of a path – both if we have to pay for using it – or if we receive some.

In general we speak of cost.Therefore one assigns cost to each part of the path – also called "edge".

Dijkstra's Algorithm computes shortest – or cheapest paths, if all cost are positive numbers. However, if one allows negative numbers, the algorithm will fail.

The Bellman-Ford Algorithm by contrast can also deal with negative cost.

Algorithm Idea

Kante vor Update — This edge is a shortcut.
We know that getting to the node on the left costs 20 units. The path from the left to the right node costs 1 unit.

Dijkstra's algorithm computes the cost of the shortest paths from a given starting node to all other nodes in the graph.

The algorithm starts at its starting node and iteratively updates the current shortest paths via the current node. The algorithm may, in the process, find shortcuts. It continues until all edges have been visited and no improvement ist possible.

The algorithm keeps the nodes that it has found, but not processed yet, in a priority queue. The nodes with the smallest distance to the starting point is the first node in the queue.

We first initialize the algorithm:

The starting point has distance 0, as its distance to itself is 0.
We don't know any path to the other nodes yes, thus their cost is set to infinity. During the course of the algorithm, these costs will be improved. The algorithm remembers the shortest path to every node.
The starting node is added to the priority queue.

Next, we remove the first node from the priority queue. In the beginning, this will be the starting node. Then all of its neighbors (with their respective edges) are considered. We check the following condition: Is this node contained in the priority queue and, if so, is the edge leading to it a shortcut?

If this is the case, then the costs for the node decrease. Otherwise, we check a second condition: Has this node already been visited? If the node has not been visited already, then it is added to the priority queue. In the future, we will inspect its neighbors as well. Furthermore, its cost is set to the sum of the cost of the edge leaving to it and the cost of its predecessor.

The algorithm continues until the priority queue is empty. When the priority queue is empty, the algorithm terminates.

Graph with distances — The green path from the starting node to node b is the cheapest path. It uses 3 edges.

Construction of the shortest path

Each time when updating the cost of some node, the algorithm saves the edge that was used for the update as the predecessor of the node.

At the end of the algorithm, the shortest path to each node can be constructed by going backwards using the predecessor edges until the starting node is reached.

If a node cannot be reached from the starting node, then its cost stays infite.

What now?

Create a graph and play through the algorithm

Test your knowledge in the exercises

SVG Download

Legend

	Starting node from where distances and shortest paths are computed.
	Node that has been chosen correctly.

Legend

How are the nodes in the priority queue ordered?

Changing the tab aborts the exercise!

You can open another browser window, to read the description in parallel.

SVG Download

Legend

	Starting node from where distances and shortest paths are computed.
	Edge with currect edge costs.
	Edge with wrong edge costs.

Legend

What are the edge costs?

Node distances:

	Start	b	c	d	e	f	g	h	i
Initiali- sation	0	∞	∞	∞	∞	∞	∞	∞	∞
Step 1		3	2	4					34
Step 2						14
Step 3					12	13
Step 4					6		8
Step 5						12	7
Step 6						8		37
Step 7								36
Step 8								35
Step 9								35

What are the edge costs?

This table shows all distances from the node to the starting node during every round of the algorithm. Some cells in the table are empty.

Can you find out the costs for these edges? Just doubleclick on an edge and set its cost.

The task is terminated if the tab is changed

You can open another browser window for reading the description in parallel.

SVG Download

Legend

	Starting node from where distances and shortest paths are computed.
	Node being processed
	Node in the priority queue
	"Predecessor edge" that is used by the shortest path to the node.

Legende

Test your knowledge: How does the algorithm decide?

rewind Forward: Next question

Explanation
Pseudocode

BEGIN

d(v[1]) ← 0

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

WHILE queue ≠ ∅ DO

u = queue.extractMin()

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, parent(w) = (u,w)

ELSE IF parent(w) == NULL THEN

d(w) = dist, parent(w) = (u,w)

queue.insert(w,dist)

END

Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

What is the pseudocode of the algorithm?

Input: Weighted, directed or undirected graph G=(V,E) 
       using poisitive weight function l.
Output: List {d(v[j]) : j = 1,..,n}, containing distances dist(v[1],v[j]) = d(v[j]).


BEGIN
    d(v[1]) ← 0
    FOR i = 2,..,n DO
        d(v[i]) ← ∞, parent(v[i]) ← NULL
    WHILE queue ≠ ∅ DO
        u = queue.extractMin()
        FOR ALL (u,w) ∈ E DO
            dist ← d(u) + l(u,w)
            IF w ∈ queue AND d(w) > dist DO
                d(w) = dist, parent(w) = (u,w)
            ELSE IF parent(w) == NULL THEN
                d(w) = dist, parent(w) = (u,w)
                queue.insert(w,dist)
END

How fast is the algorithm?

Speed of algorithms

The speed of an algorithm is the total number of individual steps which are performed during the execution.

These steps are for example:

Assignments – Set distance of a node to 20.
Comparisons – Is 20 greater than 23?
Comparison and assignment – If 20 is greater than 15, set variable n to 20
Simple Arithmetic Operations – What is 5 + 5?

Since it can be very difficult to count all individual steps, it is desirable to only count the approximate magnitude of the number of steps. This is also called the running time of an algorithm. Particularly, it is interesting to know the running time of an algorithm based on the size of the input (in this case the number of the vertices and the edges of the graph).

Running time of Dijkstra's algorithm

Assuming that the algorithm is run on a graph using n nodes and m edges.

Every node in the graph must be inspected, thus we need at least n steps.

We must extract the nodes from the priority queue before inspecting them. As extract the minimum from the priority queue n times,we need at most n · n steps for this.

Nodes are added to the priority queue, when the edges leaving some node are inspected. Based on the edge weight, the cost of nodes in the priority queue might be reduced. The algorithm therefor inspects all edges that can be reached from the starting node. This requires another m steps.

The overall running time of the algorithm, is therefore of order m + n², is we use simple list as the priority queue.

It is possible to improve the running time to m + n · log(n). This requires a more sophisticated data structure for storing the priority queue (e.g. a heap).

How do we know that the algorithm works correctly?

A proof by contradiction

As the algorithm expects only nonnegative edge costs, we can prove the following statement:All subpaths on a shortest path are also shortest paths. We can prove this statement by assuming the converse: There is a subpath of some shortest path, that is not a shortest path himself. In the following example. this could be the subpath between b and c, that lies on the shortest path from a to d.

If this subpath is not a shortest path, then there must be some other path that is even shorter. This path is shown with the orange arrow on the figure below . Now, there is a new path from a to d that uses the orange path between b and c. This new path must be shorter than the path a-b-c-d. This, however, is a contradiction to the assumtion that a-b-c-d is a shortest path.

Gegenbeispiel — The orange arrow represents some shortest path from b to c.

As we have found a contradiction to the converse of our statement, our initial statement must hold. This implies that all paths computed by our algorithm are shortest paths.

How can we deal with negative edge costs?

Exercise 3 shows that negative edge costs cause Dijkstra's algorithm to fail: it might not compute the shortest paths correctly. In the exercise, the algorithm finds a way from the stating node to node f with cost 4. However, a path of cost 3 exists.

Counterexample from exercise 3 — The graph from exercise 3

How can we deal with negative edge costs? One might try to add some constant to all costs, that is large enough to make all edge costs positive. One could, for instance, choose the cost of the cheapest edge as this constant (plus 1). In the example below, the cheapest edge has cost -2, thus we may add 2 (or 3) to all edge costs.

Negatives Beispiel — Cheapest path from a to g is a-b-c-d-e-g

Before changing the edge costs, the shortest path from a to g was a-b-c-d-e-g, with total cost -5. After changing the edge costs, the shortest path is a-f-g with total cost 6. This is problematic, as we have found a completely different path than before. This example shows us, that adding some constant to all edge costs cannot help us in case of negative edge costs.

Counterexample with positive edge costs — Shortest path from a to g is a-f-g

In order to deal with negative edge costs, we must update some nodes that have already been visited. An algorithm that can deal with this situation is the Bellman-Ford Algorithm

Where can I find more information about graph algorithms?

Other graph algorithms are explained on the Website of Chair M9 of the TU München.

Furthermore there is an interesting book about shortest paths: Das Geheimnis des kürzesten Weges

Studying mathematics at the TU München answers all questions about graph theory (if an answer is known).

A last remark about this page's content, goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the mathematical optimization of applied problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the daily research conducted at the chair reaches far beyond that point). These pages shall provide pupils and students with the possibility to (better) understand and fully comprehend the algorithms, which are often of importance in daily life. Therefore, the presentation concentrates on the algorithms' ideas, and often explains them with just minimal or no mathematical notation at all.

Please be advised that the pages presented here have been created within the scope of student theses, supervised by Chair M9. The code and corresponding presentation could only be tested selectively, which is why we cannot guarantee the complete correctness of the pages and the implemented algorithms.

Naturally, we are looking forward to your feedback concerning the page as well as possible inaccuracies or errors. Please use the suggestions link also found in the footer.

To cite this page, please use the following information:

Title: Dijkstra's Algorithm
Authors: Melanie Herzog, Wolfgang F. Riedl, Lisa Velden; Technische Universität München
Link: https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra