When computing shortest paths in graph (for example as partof a beam search) it is tempting to apply a pruned recursive algorithm. This is equivalent to performing a generic shortest path algorithm with

last-in first out LIFO queue (a stack). In an un-weighted graph this approachis fine, however in weighted graphs even with positive only weight this algorithm can have exponential worst case complexity.

The generic single source shorestpath algorihtm is shown below[1]. It assumes the input is a graph $G(V,E)$ where $V$ and $E$ denotes the vertices and edges respectively, $e$ is an edge with member $v$ for the destiantion vertex and $w$ for the edge costs, $d$ is an array of vertex (or state) costs.In the first three lines of the algorithm the array of vertex costs is initialised. The initial state of the graph is added to the queue and the then the main loop of the algorithm is run. We are interested in a stack/lifo queue, therefore the dequeue operation of line seven will remove the last vertex that was added to the queue. The algorithm then process each of the arcs leaving the state and if the destination state is lower we update the cost eleement and either add the destination to the queue or decrease the key if the state is already in the queue. For the stack in this analysis the decrease-key operation does nothing as there are no priorities in this case and we update the statce costs in line ten. (The decrease-key is needed for priority queues).

$d[0] \leftarrow 0$

$\text{for } i = 1 \dots |V| - 1 $

$\hspace{1em} d[i] \leftarrow \infty$

$Q \leftarrow s$

$\text{while } Q \neq \emptyset$

$\hspace{1em} u \leftarrow \text{Dequeue}(Q)$

$\hspace{1em} \text{for } e \in \text{adj}(Q, u)$

$\hspace{1em} \text{if } d[e.v] > d[u] + e.w$

$\hspace{2em} d[e.v] \leftarrow d[u] + e.w$

$\hspace{2em}\text{if } e.v \in Q$

$\hspace{3em}\text{Decrease-key}(Q, e.v, d[e.v])$

$\hspace{2em}\text{else}$

$\hspace{3em}\text{Enqueue}(Q, v.e)$

If we use a first-in first-out (FIFO) queue the algorithm becomes equivalent to the

Bellman-ford aglorithm. In the case of priority queue discipline the algorithm corresponds to

Dijkstra algorithm. In the remainder of this article I will explore the SSSP algorithm with a

LIFO queue and will show certain weighted graphs give rise undesirable SSSP running times.

Consider the below graph, the vertex (state) marked 0 is the initial or start state and the double circle is the final or accept vertex (state), although the algorithm is computing the shortest path from vertex zero to every other vertex we are only interested in the shortest path to state three. On inspection it easy to see the shortest path is to follow all edges with cost 0 that is the path $0\rightarrow1\rightarrow2\rightarrow3$

The below table shows the steps in the algorithm. The first column is the iteration algorithm,

the second column the element popped at that time step, the queue column is the items in the queue at the end of the current iteration and the substituent columns are the vertex costs. Here we see that for our graph that eight pops are required for the this graph as each path that has more edges but a lower

overall costs requires us to re-visit all the subsequent states again.

Time |
Pop |
Queue |
$d[0]$ |
$d[1]$ |
$d[2]$ |
$d[3]$ |

0 |
- |
0 |
$0$ |
$\infty$ |
$\infty$ |
$\infty$ |

1 |
0 |
1,2,3 |
$0$ |
$0$ |
$2$ |
$3$ |

2 |
3 |
1,2 |
$0$ |
$0$ |
$2$ |
$3$ |

3 |
2 |
1,3 |
$0$ |
$0$ |
$2$ |
$2$ |

4 |
3 |
1 |
$0$ |
$0$ |
$2$ |
$2$ |

5 |
1 |
2,3 |
$0$ |
$0$ |
$0$ |
$1$ |

6 |
3 |
2 |
$0$ |
$0$ |
$0$ |
$1$ |

7 |
2 |
3 |
$0$ |
$0$ |
$0$ |
$0$ |

8 |
3 |
$\emptyset$ |
$0$ |
$0$ |
$0$ |
$0$ |

Repeating the analysis for a FIFO queue we see that it only necessary to visit each
state once.

Time |
Pop |
Queue |
$d[0]$ |
$d[1]$ |
$d[2]$ |
$d[3]$ |

0 |
- |
0 |
$0$ |
$\infty$ |
$\infty$ |
$\infty$ |

1 |
0 |
1,2,3 |
$0$ |
$0$ |
$2$ |
$3$ |

1 |
1 |
2,3 |
$0$ |
$0$ |
$0$ |
$1$ |

1 |
2 |
3 |
$0$ |
$0$ |
$0$ |
$0$ |

1 |
3 |
$\emptyset$ |
$0$ |
$0$ |
$0$ |
$0$ |

Likewise the algorithm runs in the same time for a priority queue, however, a graph with negative weights can be constructed to yield exponential running time. For example re-weighting the graph as shown below will give the same characteristics as the LIFO queue with positive weights considered earlier

In summary when computing shortest paths the LIFO queue is fine if the graph has no weights each state only needs to be visited once. For weighted graphs either a FIFO or priority queue is a better choice, the later having better running time. Although in practise I have observed the FIFO approach consistently performing better. For graphs with negative weighted edges a priority queue can also exhibit exponential worst case running time.

[1] Jeff Erickson, "Algorithms Lecture 19: Shortest Paths", 2011,

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/19-sssp.pdf