141 lines
6.0 KiB
Plaintext
141 lines
6.0 KiB
Plaintext
'''Dijkstra's algorithm''', conceived by Dutch computer scientist [[wp:Edsger Dijkstra|Edsger Dijkstra]] in 1956 and published in 1959, is a [[wp:graph search algorithm|graph search algorithm]] that solves the single-source [[wp:shortest path problem|shortest path problem]] for a [[wp:graph (mathematics)|graph]] with non-negative [[wp:edge (graph theory)|edge]] path costs, producing a [[wp:shortest path tree|shortest path tree]].
|
|
|
|
This algorithm is often used in [[wp:routing|routing]] and as a subroutine in other graph algorithms.
|
|
|
|
|
|
For a given source [[wp:vertex (graph theory)|vertex]] (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.
|
|
|
|
|
|
;For instance:
|
|
If the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.
|
|
|
|
As a result, the shortest path first is widely used in network [[wp:routing protocol|routing protocol]]s, most notably:
|
|
::* [[wp:IS-IS|IS-IS]] (Intermediate System to Intermediate System) and
|
|
::* [[wp:OSPF|OSPF]] (Open Shortest Path First).
|
|
|
|
|
|
;Important note:
|
|
The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of '''2''' or more nodes, generally represented by:
|
|
::* an adjacency matrix or list, and
|
|
::* a start node.
|
|
|
|
|
|
A destination node is not specified.
|
|
|
|
The output is a set of edges depicting the shortest path to each destination node.
|
|
|
|
<!-- this is the original example: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
|
|
For the example we start:
|
|
<pre>
|
|
a->b,cost=7,lastNode=a; a->c,cost=9,lastNode=a; a->d,cost=NA,lastNode=a; a->e,cost=NA,lastNode=a; a->f,cost=14,lastNode=a
|
|
The lowest cost is a->b so we add a->b to the output. There is a connection from b->d so we update our input to
|
|
a->c,cost=9,lastNode=a; a->d,cost=22,lastNode=b; a->e,cost=NA,lastNode=a; a->f,cost=14,lastNode=a
|
|
The lowest cost is a->c so we add a->c to the output. Paths to d and f are cheaper via c so we update our input to
|
|
a->d,cost=20,lastNode=c; a->e,cost=NA,lastNode=a; a->f,cost=11,lastNode=c
|
|
The lowest cost is a->f so we add c->f to the output. We update our input to
|
|
a->d,cost=20,lastNode=c; a->e,cost=NA,lastNode=a
|
|
The lowest cost is a->d so we add c->d to the output. There is a connection from d->e so we update our input to
|
|
a->e,cost=26,lastNode=d
|
|
Which just leaves adding d->e to the output.
|
|
The output should now be [d->e;c->d;c->f;a->c;a->b]
|
|
</pre>
|
|
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ !-->
|
|
|
|
;An example, starting with:
|
|
<syntaxhighlight lang="text"> a──►b, cost=7, lastNode=a
|
|
a──►c, cost=9, lastNode=a
|
|
a──►d, cost=NA, lastNode=a
|
|
a──►e, cost=NA, lastNode=a
|
|
a──►f, cost=14, lastNode=a
|
|
|
|
The lowest cost is a──►b so a──►b is added to the output.
|
|
|
|
There is a connection from b──►d so the input is updated to:
|
|
a──►c, cost=9, lastNode=a
|
|
a──►d, cost=22, lastNode=b
|
|
a──►e, cost=NA, lastNode=a
|
|
a──►f, cost=14, lastNode=a
|
|
|
|
The lowest cost is a──►c so a──►c is added to the output.
|
|
|
|
Paths to d and f are cheaper via c so the input is updated to:
|
|
a──►d, cost=20, lastNode=c
|
|
a──►e, cost=NA, lastNode=a
|
|
a──►f, cost=11, lastNode=c
|
|
|
|
The lowest cost is a──►f so c──►f is added to the output.
|
|
|
|
The input is updated to:
|
|
a──►d, cost=20, lastNode=c
|
|
a──►e, cost=NA, lastNode=a
|
|
|
|
The lowest cost is a──►d so c──►d is added to the output.
|
|
|
|
There is a connection from d──►e so the input is updated to:
|
|
a──►e, cost=26, lastNode=d
|
|
|
|
Which just leaves adding d──►e to the output.
|
|
|
|
The output should now be:
|
|
[ d──►e
|
|
c──►d
|
|
c──►f
|
|
a──►c
|
|
a──►b ] </syntaxhighlight>
|
|
|
|
|
|
;Task:
|
|
# Implement a version of Dijkstra's algorithm that outputs a set of edges depicting the shortest path to each reachable node from an origin.
|
|
# Run your program with the following directed graph starting at node <big> '''a'''.</big>
|
|
# Write a program which interprets the output from the above and use it to output the shortest path from node <big> '''a''' </big> to nodes <big> '''e''' </big> and <big> '''f'''. </big>
|
|
|
|
::::::::: {| class="wikitable" style="text-align: center; float: left"
|
|
|+ Vertices
|
|
|-
|
|
! Number !! Name
|
|
|-
|
|
| 1 || a
|
|
|-
|
|
| 2 || b
|
|
|-
|
|
| 3 || c
|
|
|-
|
|
| 4 || d
|
|
|-
|
|
| 5 || e
|
|
|-
|
|
| 6 || f
|
|
|}
|
|
{| class="wikitable" style="text-align: center"
|
|
|+ Edges
|
|
|-
|
|
! Start !! End !! Cost
|
|
|-
|
|
| a || b || 7
|
|
|-
|
|
| a || c || 9
|
|
|-
|
|
| a || f || 14
|
|
|-
|
|
| b || c || 10
|
|
|-
|
|
| b || d || 15
|
|
|-
|
|
| c || d || 11
|
|
|-
|
|
| c || f || 2
|
|
|-
|
|
| d || e || 6
|
|
|-
|
|
| e || f || 9
|
|
|}
|
|
|
|
|
|
You can use numbers or names to identify vertices in your program.
|
|
|
|
|
|
;See also
|
|
* [https://www.youtube.com/watch?v=cSxnOm5aceA Dijkstra's Algorithm vs. A* Search vs. Concurrent Dijkstra's Algorithm (youtube)]
|
|
<br><br>
|
|
|