Dijkstra’s Shortest Path Algorithm Example

Dijkstra’s shortest path algorithm finds the shortest paths between all nodes of the graph. In this article we will describe the operation principle of Dijkstra’s algorithm, which finds optimal routes. The disadvantage of this algorithm is that it will not work correctly if the graph has negative edge weights. In this tutorial you can read Dijkstra’s shortest path algorithm example. The author has solved a particular task and provided a vivid description of the solution. Following each step you will be able to solve a similar solution by yourself with ease.

With our Dijkstra’s shortest path algorithm example you can learn how to create and solve similar tasks. Look attentively to each step and highlight the important points that you need to consider while solving such an assignment. On our blog you can find various samples connected with this and other topics. Our service helps hundreds of students that have troubles with assignments in various disciplines: programming, mathematics, chemistry, physics, statistics, and more. If for some reason you can’t manage the assignment by yourself you can ask our writers for online assignment help.

Dijkstra’s Shortest Path Algorithm Task

Task: find all the shortest paths from the vertex # 1 for the graph shown in the figure below using the Dijkstra algorithm.

Solution:

First, we form the matrix of lengths of shortest arcs for a given graph.

The starting vertex from which the tree of shortest paths is constructed is the vertex 1.

We set the starting conditions:

$d (1) = 0, d (x) = \infty$

We color vertex 1, $y = 1$ .

We find the nearest vertex to the one that was colored by us, using the formula:

$d (2) = min \{d (2); d (1) + a (1,2)\} = min \{\infty; 0+10\} = 10$
$d (3) = min \{d (3); d (1) + a (1,3)\} = min \{\infty; 0+18\} = 18$
$d (4) = min \{d (4); d (1) + a (1,4)\} = min \{\infty; 0+8\} = 8$
$d (5) = min \{d (5); d (1) + a (1,5)\} = min \{\infty; 0+\infty\} = \infty$
$d (6) = min \{d (6); d (1) + a (1,6)\} = min \{\infty; 0+\infty\} = \infty$

The minimum length has a path from vertex 1 to vertex 4 $d (4) = 8$ . We include the vertex # 4 in the current oriented tree, as well as the arc leading to this vertex.

$d (2) = min \{d (2); d (4) + a (4,2)\} = min \{10; 8+9\} = 10$
$d (3) = min \{d (3); d (4) + a (4,3)\} = min \{18; 8+\infty\} = 18$
$d (5) = min \{d (5); d (4) + a (4,5)\} = min \{\infty; 8+\infty\} = \infty$
$d (6) = min \{d (6); d (4) + a (4,6)\}= min \{\infty; 8+12\} = 20$

The minimum length is the path from vertex 1 to vertex 2 $d (2) = 10$ . We include vertex # 2 in the current oriented tree, as well as the arc leading to this vertex. According to the expression this is the arc (1,2).

$d (3) = min \{d (3); d (2) + a (2,3)\} = min \{18; 10+16\} = 18$
$d (5) = min \{d (5); d (2) + a (2,5)\} = min \{\infty; 10+21\} = 31$
$d (6) = min \{d (6); d (2) + a (2,6)\} = min \{20; 10+\infty\} = 20$

The minimum length is the path from vertex 1 to vertex 3 $d (3) = 18$ . We include vertex # 3 in the current oriented tree, as well as the arc leading to this vertex. According to the expression, this is the arc (1.3).

$d (5) =min \{d (5); d (3) +a (3,5)\} =min \{31; 18+15\} = 31$
$d (6) =min \{d (6); d (3) +a (3,6)\} =min \{20; 18+\infty\} = 20$

The minimum length is the path from vertex 1 to vertex 6 $d (6) = 20$ . We include the vertex # 6 in the current oriented tree, as well as the arc leading to this vertex. According to the expression, this is the arc (4.6).

$d (5) = min \{d (5); d (6) + a (6,5)\} = min \{31; 20+23\} = 31$

The minimum length is the path from vertex 1 to vertex 5 $d (5) = 31$ . We include vertex # 5 in the current oriented tree, as well as the arc leading to this vertex. According to the expression, this is the arc (2.5). We have obtained an oriented tree of the shortest paths starting at vertex # 1 for the original graph.

$d (1) = 1$ The length of the route $L = 0$
$d (2) = 1-2$ The length of the route $L = 10$
$d (3) = 1-3$ Length of the route $L = 18$
$d (4) = 1-4$ The length of the route $L = 8$
$d (5) = 1-2-5$ The length of the route $L = 31$
$d (6) = 1-4-6$ The length of the route $L = 20$