Re: [理工] [DS] single source shortest path

[FRAXIS (喔喔)]

※ 引述《jim055006 (jim)》之銘言：
: 題目如下:
: We have a directed graph G=(V,E) represented using adjacency list.
: The edge costs are integers in the range {1,2,3,4,5}. Assume that
: G has no self-loops or mutiple edges. Design an algorithm that
: solves the single-source shortest path problem in G in O(|V|+|E|).
: 答案為:
: DAG-Shortest-Path(G,w,s)
:   {
:    Topologically sort V[G]
:    Initialize-Single-Source(G,s)
:    For each u taken in topological order do
:         for each v€adj[u] do
:           {
:            if d[v]>d[u]+w(u,v) then
:               d[v]=d[u]+w(u,v)
:           }
:    }

其實這個解法很奇怪，因為只有圖在沒有迴圈的時候才有Topological Order。
但是題目並沒有說圖是DAG，所以這解法不對。

我的想法是利用BFS，既然每條邊的上限都只有5，就把每條邊換成4個點+5條邊，
這樣並不會增加圖的大小太多，然後圖就變成無權重圖了。
無權圖上找最短路徑可用BFS在線性時間解出。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
推 jim055006:哦...題目有說loop-free喔...且無多重邊...
→ FRAXIS:只是no self-loop 不是acyclic 兩者是不同的
推 jim055006:喔喔....因為我看你打迴路就想成是loop...
→ jim055006:確實要是有cycle的話不會有拓樸排序....
→ jim055006:不知道F大可否將你的想法寫成algo看一下呢??
推 jim055006:感謝F大細心的提點!!!!