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{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$

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.

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$ |

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

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é.

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.

jianbin0222

coach outletlouis vuitton outlet storepandora outletcalvin klein underwearmichael kors handbagscheap jordansnike free 5rolex ukabercrombie and fitchmichael kors wholesaleabercrombie and fitchvans shoescheap ray ban sunglassescheap jordan shoesray ban sunglassesed hardy clothingralph lauren outletnike air huarachetiffany jewelleryinstyler ionic stylermichael kors uk outletmichael kors ukcheap nfl jerseyscheap mlb jerseysmichael kors online outletadidas wingsadidas outlet storemichael kors outletmichael kors outlet onlinelongchamp handbagscoach outlet onlinecamisetas futbol baratasherve leger dresseslouis vuitton neverfull salekate spade handbagsfitflops saleoakley sunglassesnike air huaracheray ban sunglassesfootball shirtstrue religion jeanstimberland shoeshermes birkin bagrolex ukfitflop clearancecheap jordan shoeslouis vuitton bags cheapmulberry outletmcm backpacktrue religion jeansnfl jerseys wholesalefitflops clearanceair force 1 shoespolo ralph laurenair max 2015louis vuitton handbagsnike huarachechristian louboutin onlineoakley sunglasseskobe bryants shoeslebron james shoesmichael kors outlet onlinecheap ray ban sunglasseshermes beltmichael kors outlet online20160415zhenhong

lebron shoesoncheap nhl jerseysFridayhouston texans jerseystopnike roshehowmichael kors handbagsWechiefs jerseyhowasics shoesformichael kors handbagsherepandora jewelrypostmichael kors outletyourkate spade outlet onlineed hardy outletmichael kors handbags clearanceugg pas chernike cortez classicadidas nmd r1red bottomcoach outlet onlineadidas superstarscoach factory outlet onlinezhi20170103

coach outlet onlinemichael kors outletlouis vuittonnhl jerseysugg outletray ban sunglassesnike outletmichael kors outletmonclercanada goose outlet20171.03wengdongdong