View source for Epita: Algo: Course: Info-Spe: shortest path algorithms

== Overview==
''<u>Remarks and definitions:</u>''
* ''We will focus on the non zero-length paths.''
* ''We will work with edge-weighted directed graphs.''
* ''The cost (weight or value) of a path is equal to the sum of the cost of the arcs that compose it. We call it '''the distance''' of the path.''
* ''The shortest path from a vertex '''x''' to a vertex '''y''' is the minimum cost path from '''x''' to '''y'''. Such a path does not necessarily exist.''
* ''The shortest distance from a vertex '''x''' to a vertex '''y''' is the cost of the shortest path if it exists.''

<br/>

''<u>Conditions of existence:</u>''

Consider a path '''''M''''' from a vertex '''''x''''' to a vertex '''''y'''''. Suppose this path contains a circuit '''''T'''''. Call '''''M'''''' the obtained path removing '''''T''''' of '''''M'''''. We then have the following cost relation:
 Cost('''''M''''') = Cost('''''M'''''') + Cost('''''T''''')
If the Cost('''''T''''') is negative (<0), there exists no shortest path from '''''x''''' to '''''y'''''. Indeed, it is sufficient to simply cross the circuit '''''T''''' again to get a better result (lower cost path).

''Such a circuit is called '''negative (directed) cycle'''.''

If the Cost('''''T''''') is zero (=0), '''''M'''''' has the same cost than '''''M'''''. In this case it is also a shortest path but its length (number of vertices crossed) is greater than the one of '''''M'''''.

If the Cost('''''T''''') is positive (>0), the Cost of '''''M'''''' is less than the one of '''''M'''''. In this case it is a better candidate than '''''M''''' for the shorstest path.

If there exist circuits, their cost is positive or zero. But a shortest path can not contain a positive cost circuit and if there exist nul cost circuits, there are several solutions to the problem.

Since the number of elementary paths (in which all vertices are distinct) from a vertex '''''x''''' to a vertex '''''y''''' is finite, there exists at least one elementary shortest path from '''''x''''' to '''''y''''' (''remark: There may be several'').
<br/>

'''''In conclusion: There exists a solution to the shortest path problem from '''''x''''' to '''''y''''' if there exists a path from '''''x''''' to '''''y''''' and there is no negative cycle.'''''

<br/>

''<u>Variants of the problem:</u>''

The algorithms we present give, in the case where there is no negative cycle, un elementary shortest path.

The three ways of searching for a shortest path are: 
# between two vertices '''''x''''' and '''''y''''',
# from a vertex '''''x''''' (a source) to all the other vertices of the graph,
# between all pairs of vertices '''''x''''' and '''''y'''''.

<br/>

''Remarks:''
* ''The 1) is considered as the best solution of the 2), we focus only on the 2) and 3).''
* ''There is no general algorithm for the 2) nor for the 3). It is necessary to consider the properties of the manipulated graphs and the problem posed and then choose the most suitable algorithm.''
<br/>

==Dijkstra==
The Dijkstra algorithm is usable only in the very frequent cases where the cost of the arcs are positive or zero. It determines the shortest path between a source vertex '''''x''''' and all the other vertices of the graph reachable from '''''x'''''.
Then we obtain a tree of root '''''x''''' formed by the shortest paths from '''''x''''' to the vertices reachable by '''''x'''''. It should be noted that, having no negative costs, it accepts graphs containing circuits.

===Principle===
Let '''''G=< S,A,C >''''' be a weighted directed graph of '''''n''''' vertices.
Let '''''x''''' be a vertex of '''''S'''''. It is proposed to build a set '''''SP''''' (shortest path) of vertices '''''y''''' for which the shortest path from '''''x''''' is known.

* Initially, '''''SP''''' only contains the source ('''''x''''').
* At each step a vertex '''''y''''', for which the smallest distance ('''sdistance(''x,y,G'')''') and the parent ('''parent(''x,y,G'')''') are known, is added to '''''SP'''''.
* We stop when '''''SP''''' contains all vertices reachable from '''''x'''''.

Let '''''M''''' be the complement set of '''''SP''''' in '''''S''''' ('''''M=S-SP''''') and for all vertices '''''y''''' of '''''M''''', we call '''path from ''x'' to ''y'' in ''SP''''' any path from  '''''x''''' to '''''y''''' having only vertices of '''''SP''''' except '''''y''''' (see figure 1.).

{| align="center" border="1" cellpadding="10"
|+ '''Figure 1. Paths from ''x'' to ''y'' in ''SP'''''.
|  align="center" | [[Image:spath_dijkstra_1.png| 250px | ''Path from x to y in SP.'']]
|}
<br/>

We write '''distance<sub>''x,SP''</sub>(''y'')''', the cost of the shortest path from '''''x''''' to '''''y''''' in '''''SP''''' and '''pred<sub>''x,SP''</sub>(''y'')''' the predecessor of '''''y''''' in this shortest path.

At each step, we choose a vertex '''''m''''' of '''''M''''' such as:
 '''distance<sub>''x,SP''</sub>(''m'') = Min{'''distance<sub>''x,SP''</sub>(''y'')'''} <math>\forall y \in M</math>'''

===Algorithm===

The algorithm traverses the graph '''''g''''' from a source vertex '''''x''''' and returns two arrays: '''''sp''''' and '''''pr''''' to memorize the shortest paths and their respective distance. '''''sp[y]''''' will memorize '''distance<sub>''x,SP''</sub>(''y'')''' and '''''pr[y]''''' will memorize '''pred<sub>''x,SP''</sub>(''y'')'''.

To avoid useless tests, we will extend the capabilities of the cost function to be defined for all pairs of vertices ('''''x,y''''') as follows:
 '''cost(''x,x,g'') = 0''' for a graph without loop
 <br/>
 '''cost(''x,y,g'') = <math>\infty</math>''' if <''x'',''y''> isanarcof ''g'' = false

We will also use an operation '''choosemin(''M, sp'')''' which will return the vertex <math>m\in M</math> such as sp[m] is minimum, and the operations on sets. 

For the Dijkstra algorithm, the data type used are the following:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    Nbv = ...                           <span style="color:#999999;">/* Vertices Number of the graph */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_vectNbvReal = Nbv real            <span style="color:#999999;">/* Vector of Nbv real */</span>
    t_vectNbvInt  = Nbv integer         <span style="color:#999999;">/* Vector of Nbv integer */</span>

That gives:

 '''Algorithm procedure''' Dijkstra
 '''Local parameters'''
    integer x                           <span style="color:#999999;">/* x is the source vertex */</span>
    graph g
 '''Global parameters'''
    t_vectNbvReal sp                    <span style="color:#999999;">/* sp[y] is the distance of the shortest path from x to y*/</span>
    t_vectNbvInt  pr                    <span style="color:#999999;">/* pr[y] is the predeécessor of y in this path */</span>
 '''Variables'''
    integer i, y, m                     <span style="color:#999999;">/* y and m are vertices */</span>
    real v
    set M
 '''Begin'''
    <span style="color:#999999;">/* Initialization */</span>
    M <math>\leftarrow</math> emptyset
    '''for''' i <math>\leftarrow</math> 1 '''to''' n '''do'''
       sp[i] <math>\leftarrow</math> cost(x,i,g)
       pr[i] <math>\leftarrow</math> x
       M <math>\leftarrow</math> insert(i,M)
    '''endfor'''
    M <math>\leftarrow</math> delete(x,M)                      <span style="color:#999999;">/* SP={x} */</span>
    <span style="color:#999999;">/* Successive insertions of vertices to SP */</span>
    '''while''' M <> emptyset '''do'''
       m <math>\leftarrow</math> choosemin(M,sp)
       '''if''' sp[m] = <math>\infty</math> '''then'''                   <span style="color:#999999;">/* no more reachable vertex from x */</span>
          '''return'''
       '''endif''' 
       M <math>\leftarrow</math> delete(m,M)                      <span style="color:#999999;">/* insertion of m to SP */</span>
       <span style="color:#999999;">/* adjustment of the distance values */</span>
       '''for''' i <math>\leftarrow</math> 1 '''to''' d<sup>o+</sup>(m,g) '''do'''
          y <math>\leftarrow</math> nthsucc(i,m,g)
          '''if''' y <math>\in</math> M '''then'''                     <span style="color:#999999;">/* the shortest path from x to y is not already determined */</span>
             v <math>\leftarrow</math> sp[m] + cost(m,y,g)
             '''if''' v < sp[y] '''then'''   
                sp[y] <math>\leftarrow</math> v
                pr[y] <math>\leftarrow</math> m
             '''endif'''
          '''endif'''
       '''endfor'''
    '''endwhile'''
 '''End algorithme procedure''' Dijkstra
<br/>

Apply the Dijsktra algorithm to the weighted directed graph of the figure 2 using the vertex '''''1''''' as source vertex (we search to determine the shortest paths from '''''1''''' to all the others.)
 
''Remark: the vertices are treated in increasing order, whether in the set '''M''' or as successors.''
<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 2. Weighted directed graph ''G''.'''
|  align="center" | [[Image:diskstragraphref.png|350px | ''weighted directed graph'']]
|}
<br/>

After the execution of '''Dijkstra''' algorithm, we obtain the vectors '''''sp''''' and '''''pr''''' as follows (table 1):

{| align="center" border="1" cellpadding="10"
|+ '''Table 1. Vectors ''sp'' and ''pr'' resulting from the application of the Dijkstra algorithm applied to the graph of Figure 2.'''
| align="right" | Vertices (index)
| align="left" | 1
| align="left" | 2
| align="left" | 3
| align="left" | 4
| align="left" | 5
| align="left" | 6
| align="left" | 7
| align="left" | 8
|-
| align="right" | SP
| align="center" | 0
| align="center" | 1
| align="center" | 0
| align="center" | 2
| align="center" | 1
| align="center" | 3
| align="center" | 2
| align="center" | 2
|-
| align="right" | PR
| align="center" | 1
| align="center" | 3
| align="center" | 1
| align="center" | 2
| align="center" | 3
| align="center" | 5
| align="center" | 1
| align="center" | 7
|}
<br/>

That corresponds to the tree of root '''''1''''' as follows (see Figure 3):

{| align="center" border="1" cellpadding="10"
|+ '''Figure 3. Tree of the shortest paths from ''1''.'''
|  align="center" | [[Image:dijsktraobtainedtree.png |170px | ''Tree of the shortest paths.'']]
|}
<br/>

For instance, to know the shortest path from vertex '''''1''''' to vertex '''''4''''', it is sufficient to go back from vertex '''''4''''' (destination) to vertex '''''1''''' (the source) using vector '''pr''', its cost (shortest distance) being obtained by '''sp[''4'']''', which gives:

 shortest path from 1 to 4 : 1<math>\rightarrow</math>3<math>\rightarrow</math>2<math>\rightarrow</math>4 of cost: 2
<br/>

==Bellman==
The Bellman algorithm is usable in cases where the costs of the arcs are of any kind, but where the graph does not have a circuit. It determines the shortest path between a source vertex '''''x''''' (root of the graph) and all the other vertices of the graph reachable from '''''x'''''. Then we obtain a tree of root '''''x''''' formed by the shortest paths from '''''x''''' to the vertices reachable by '''''x'''''.

===Principle===
Let '''''G=< S,A,C >''''' be a weighted directed graph of '''''n''''' vertices.
Let '''''x''''' be a vertex of '''''S''''', we shall build a set '''''SP''''' (shortest path) of vertices '''''y''''' for which the shortest path from '''''x''''' is known.
Let '''''M''''' be the complement set of '''''SP''''' in '''''S''''' ('''''M=S-SP'''''). '''''M''''' is the set of vertices '''''y''''' for which '''sdistance(''x,y,G'')''' is not already known. 

We can calculate '''sdistance(''x,y,G'')''' only when all the predecessors of '''''y''''' are in '''''SP'''''.

<math>\Rightarrow \forall y \in S,</math> it is necessary to know its indegree (number of predecessors) and to be able to access to its i<sup>th</sup> predecessor.

<br/>

<u>The idea is as follows:</u>

A shortest path from  '''''x''''' to '''''y''''' must pass by  '''''m''''', one of the predecessors of '''''y''''' (see figure 4). The predecessor for which '''sdistance(''x,m,G'') + cost(''m,y,G'')''' is minimum.

{| align="center" border="1" cellpadding="10"
|+ '''Figure 4. Paths from ''x'' to ''y'' in ''SP'''''.
|  align="center" | [[Image:Spath_dijkstra_1.png |250px | ''Path from x to y in SP.'']]
|}
<br/>

===Algorithm===

The algorithm returns two arrays: '''''sp''''' and '''''pr''''' to memorize the shortest paths and their respective distance. '''''sp[y]''''' will memorize '''distance<sub>''x,SP''</sub>(''y'')''' and '''''pr[y]''''' will memorize '''pred<sub>''x,SP''</sub>(''y'')'''.

To avoid useless tests, we will extend the capabilities of the cost function to be defined for all pairs of vertices ('''''x,y''''') as follows:
 '''cost(''x,x,g'') = 0''' for a graph without loop
 <br/>
 '''cost(''x,y,g'') = <math>\infty</math>''' if <''x'',''y''> isanarcof ''g'' = false

* Initially, '''''SP''''' contains only the source ('''''x''''').
* At each step the algorithm chooses in '''''M''''' a vertex '''''y''''' for which all predecessors are in '''''SP'''''. We search by which of its predecessors the path from '''''x''''' is the shortest. Then this vertex is added to '''''SP''''' and the vectors '''sp''' and '''pr''' are updated.
* We stop when '''''M''''' is empty.

We will use the operation '''choosenext(''M, g'')''' which will return the vertex <math>m\in M</math> that has no more predecessors in '''''M'''''. 

For the Bellman algorithm, the data type used are the following:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    Nbv = ...                           <span style="color:#999999;">/* Vertices Number of the graph */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_vectNbvReal = Nbs real            <span style="color:#999999;">/* Vector of Nbv real */</span>
    t_vectNbvInt  = Nbs integer         <span style="color:#999999;">/* Vector of Nbv integer */</span>

That gives:

 '''Algorithm procedure''' Bellman
 '''Local parameters'''
    integer x                           <span style="color:#999999;">/* x is the source vertex */</span>
    graph g
 '''Global parameters'''
    t_vectNbvReal sp                    <span style="color:#999999;">/* sp[y] is the distance of the shortest path from x to y*/</span>
    t_vectNbvInt  pr                    <span style="color:#999999;">/* pr[y] is the predeécessor of y in this path */</span>
 '''Variables'''
    integer i, y, z, m                  <span style="color:#999999;">/* y, z and m are vertices */</span>
    real min, aux                       <span style="color:#999999;">/* min and aux are distances */</span>
    set M
 '''Begin'''
    <span style="color:#999999;">/* Initialization */</span>
    M <math>\leftarrow</math> emptyset
    '''for''' i <math>\leftarrow</math> 1 '''to''' n '''do'''
       M <math>\leftarrow</math> insert(i,M)
    '''endfor'''
    M <math>\leftarrow</math> delete(x,M)                      <span style="color:#999999;">/* SP={x} */</span>
    sp[x] <math>\leftarrow</math> 0
    pr[x] <math>\leftarrow</math> x
    <span style="color:#999999;">/* Successive insertions of vertices to SP */</span>
    '''while''' M <> emptyset '''do'''
       m <math>\leftarrow</math> choosenext(M,g)
       M <math>\leftarrow</math> delete(m,M)                      <span style="color:#999999;">/* insertion of m to SP */</span>
       y <math>\leftarrow</math> nthpred(1,m,g)                   <span style="color:#999999;">/* First predecessor and its associated distance */</span>
       min <math>\leftarrow</math> sp[y] + cost(y,m,g)
       <span style="color:#999999;">/* comparison with the other predecessors */</span>
       '''for''' i <math>\leftarrow</math> 2 '''to''' d<sup>o-</sup>(m,g) '''do'''
          z <math>\leftarrow</math> nthpred(i,m,g)                <span style="color:#999999;">/* ith predecessor and its associated distance */</span>
          aux <math>\leftarrow</math> sp[z] + cost(z,m,g)
          '''if''' aux < min '''then'''                 <span style="color:#999999;">/* the shortest path from x to y is not already determined */</span>
             min <math>\leftarrow</math> aux
             y <math>\leftarrow</math> z
          '''endif'''
       '''endfor'''
       sp[x] <math>\leftarrow</math> min
       pr[x] <math>\leftarrow</math> y
    '''endwhile'''
 '''End algorithm procedure''' Bellman
<br/>

Apply the Bellman algorithm to the weighted directed graph of figure 5 using the vertex '''''1''''' as source vertex (We are trying to determine the shortest paths from '''''1''''' to all the others.)
 
''Remark: the vertices are treated in increasing order, whether in the set '''M''' or as successors.''

<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 5. Directed weighted graph ''G'' with any costs (without circuit).'''
|  align="center" | [[Image:bellmangraphref.png|350px | ''Directed weighted graph with any costs (without circuit)'']]
|}
<br/>

After the execution of '''Bellman''' algorithm, we obtain the vectors '''''sp''''' and '''''pr''''' as follows (table 2):

{| align="center" border="1" cellpadding="10"
|+ '''Table 2. Vectors ''sp'' et ''pr'' resulting from the application of the Bellman algorithm applied to the graph of Figure 5.'''
| align="right" | Vertices (index)
| align="left" | 1
| align="left" | 2
| align="left" | 3
| align="left" | 4
| align="left" | 5
| align="left" | 6
| align="left" | 7
| align="left" | 8
|-
| align="right" | SP
| align="center" | 0
| align="center" | -1
| align="center" | 0
| align="center" | -3
| align="center" | 1
| align="center" | -5
| align="center" | -2
| align="center" | -2
|-
| align="right" | PR
| align="center" | 1
| align="center" | 5
| align="center" | 1
| align="center" | 5
| align="center" | 3
| align="center" | 8
| align="center" | 1
| align="center" | 7
|}
<br/>

That corresponds to the tree of root '''''1''''' as follows (see Figure 6):

{| align="center" border="1" cellpadding="10"
|+ '''Figure 6. Tree of the shortest paths from ''1''.'''
|  align="center" | [[Image:bellmanobtainedtree.png |170px | ''Tree of the shortest paths.'']]
|}
<br/>

For instance, to know the shorstest path from vertex '''''1''''' to vertex '''''4''''', it is sufficient to go back from vertex '''''4''''' (destination) to vertex '''''1''''' (the source) using vector '''pr''', its cost (shortest distance) being obtained by '''sp[''4'']''', which gives:

 shortest path from 1 to 4 : 1<math>\rightarrow</math>3<math>\rightarrow</math>5<math>\rightarrow</math>4 of cost: -3
<br/>

==Floyd==
The Floyd algorithm is usable in cases where the costs of the arcs are of any kind, with or without circuit but without negative circuit. It determines the shortest path between all pairs of vertices ('''''x,y''''') of a graph '''''G'''''.

''We can use the [[Epita:_Algo:_Course:_Info-Spe:_shortest_path_algorithms#Bellman|'''Bellman''']] or the [[Epita:_Algo:_Course:_Info-Spe:_shortest_path_algorithms#Dijkstra|'''Dijkstra''']] algorithms by varying the root, but not for graphs with any costs and having non negative circuits.''

The Floyd algorithm is one of simple algorithms which determine all the shortest paths using a matrix representation.

===Principle===
The principle of this algorithm is the same as [[Epita:_Algo:_Course_Info-Spe:_Connectivities#WARSHALL Algorithm|'''The Warshall algorithm''']] used to determine the transitive closure of a graph (''connectivity of the graph'').

Let '''''G=< S,A,C >''''' be a weighted directed graph of '''''n''''' vertices.

* Initially, we consider only the paths '''''x''''' to '''''y''''' that do not go through other vertices of the graph. Then we have '''sdistance(''x,y,G'') = cost(''x,y,G'')''' an '''parent(''x,y,G'') = ''x'''''. 
* At each step '''''i''''', we calculate '''distance<sub>i</sub>(''x,y'')''' the cost of the shortest path from '''''x''''' to '''''y''''' going through vertices that are less or equal to '''''i'''''. If this distance is less than the current known shortest distance, it becomes this shortest distance and '''parent(''i,y,G'')''' replaces '''parent(''x,y,G'').

===Algorithm===

The algorithm will use two matrices: '''''sp''''' and '''''pr''''' to memorize the shortest paths and their respective distance. '''''sp[x,y]''''' will memorize '''sdistance<sub>''i''</sub>(''x,y'')''' and '''''pr[x,y]''''' will memorize '''parent<sub>''i''</sub>(''x,y'')'''.

To avoid useless tests we will extend the capabilities of the cost function to be defined for all pairs of vertices ('''''x,y''''') as follows:
 '''cost(''x,x,g'') = 0''' for a graph without loop
 <br/>
 '''cost(''x,y,g'') = <math>\infty</math>''' if <''x'',''y''> isanarcof ''g'' = false

* Initially '''''sp''''' and '''''pr''''' are respectively initialized by '''cost(''x,y,G'')''' and '''''x'''''. 
* At each step '''''i''''', these two matrices are updated by some possible shortest paths encountered going through vertices less than or equal to '''''i'''''.
For the Floyd algorithm, the data type used are the following:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    Nbv = ...                                   <span style="color:#999999;">/* Vertices Number of the graph */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_matNbvNbvReal = Nbv x Nbv real            <span style="color:#999999;">/* Square matrix of Nbv real */</span>
    t_matNbvNbvInt  = Nbv x Nbv integer         <span style="color:#999999;">/* Square matrix of Nbv integer */</span>

That gives:

 '''Algorithm procedure''' Floyd
 '''local parameters'''
    graph g
 '''global parameters'''
    t_matNbvNbvreal ppd                  <span style="color:#999999;">/* Adjacency matrix of the graph g */</span>
    t_matNbvNbvint pr                    <span style="color:#999999;">/* Adjacency matrix of the graph g* */</span>
 '''Variables'''
    integer i, x, y                      <span style="color:#999999;">/* i, x and y are vertices */</span>
 '''begin'''
    <span style="color:#999999;">/* Initialization of sp and pr */</span>    
    '''for''' x <math>\leftarrow</math> 1 '''to''' Nbv '''do''' 
       '''for''' y <math>\leftarrow</math> 1 '''to''' Nbv '''do'''
          sp[x,y] <math>\leftarrow</math> cost(x,y,g)
          pr[x,y] <math>\leftarrow</math> x
       '''endfor'''
    '''endfor'''<br/>
    <span style="color:#999999;">/* Calculation of the shortest paths */</span>    
    '''for''' i <math>\leftarrow</math> 1 '''to''' Nbv '''do'''
       '''for''' x <math>\leftarrow</math> 1 '''to''' Nbv '''do'''
          '''for''' y <math>\leftarrow</math> 1 '''to''' Nbv '''do'''
             '''if''' sp[x,i] + sp[i,y] < sp[x,y] '''then'''
                sp[x,y] <math>\leftarrow</math> sp[x,i] + sp[i,y]
                pr[x,y] <math>\leftarrow</math> pr[i,y]
             '''endif''' 
          '''endfor'''
       '''endfor'''
    '''endfor'''
 '''end algorithm procedure''' Floyd

Apply the Floyd algorithm to the weighted directed graph of the figure 7.
<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 7. Weight directed graph ''G''  with any costs and circuits.'''
|  align="center" | [[Image:floydgraphref.png|350px | ''Weight directed graph with any costs and circuits'']]
|}
<br/>

After running the '''Floyd''' algorithm, we obtain the matrices '''''sp''''' and '''''pr''''' as follows (table 3):

{| align="center" border="1" cellpadding="10"
|+ '''table 3. Evolutions of the matrices ''sp'' and ''pr'' during the application of the Floyd algorithm to the graph of the figure 7.'''
|  align="center" | [[Image:floyd_matrices_6sommets2.png|500px | ''Evolutions of the matrices sp and pr'']]
|}
<br/>

For instance, to know the shortest path from vertex '''''6''''' to vertex '''''3''''', it is sufficient to go back from vertex '''''3''''' (destination) to vertex '''''6''''' (the source) using vector '''pr''', its cost (shortest distance) being obtained by '''sp[''6,3'']''', which gives:

<br/>
 pr[6,3] (4)
 pr[6,4] (2)
 pr[6,2] (1)
 pr[6,1] (6)
 <br/>
 The the shortest path from 6 to 3 is: 6 -> 1 -> 2 -> 4 -> 3 of cost sp[6,3]: 4
----
<small>''(Christophe "krisboul" Boullay)''</small>