'''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 &nbsp; <big> '''a'''.</big>
# Write a program which interprets the output from the above and use it to output the shortest path from node &nbsp; <big> '''a''' </big> &nbsp; to nodes &nbsp; <big> '''e''' </big> &nbsp; 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>