Shortest Paths in Weighted Graphs using a Stack

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

This entry was posted by Edobashira. Bookmark the permalink.

7 thoughts on “Shortest Paths in Weighted Graphs using a Stack”

  1. Làm sao để gửi hàng đi miền tây? Nếu đây là điều bạn đang thắc mắc thì hãy đến với chúng tôi. Chúng tôi là công ty chuyên nhận vận chuyển hàng. Các dịch vụ của chúng tôi hiện đang được rất nhiều ủng hộ. Và đây là những dịch vụ tiêu biểu được nhiều sử dụng của chúng tôi: giá giao hàng nhanh tốt nhất, giao hàng nhanh tphcm, nhận ký gửi hàng hóa, dịch vụ giao hàng thu tiền cod, ship hàng nội thành, gửi hàng về miền tây, chuyển hàng về đà nẵng, dịch vụ chuyển hàng. Nếu bạn đang cần vận chuyển hay sử dụng dịch vụ giao hàng nội thành hãy liên hệ với chúng tôi nhé.

  2. Nếu bạn đang muốn đăng tin bán nhà hay bán đất hoặc bạn muốn mua nhà hay đất thì hãy đến với chúng tôi rao vat mien phi, với chất lương hàng đầu chúng tôi sẽ giúp các bạn , đăng tin và xem các khu vực nha dat quan go vap, ban dat quan 9, nha dat quan thu duc , nha dat quan binh tan , nha dat quan tan phu , nha dat quan tan binh và các khu vực khác trên toàn quốc với uy tín và hiệu quả cao khi bạn đến với chúng tôi.

Leave a Reply

Note: only a member of this blog may post a comment.