題目：
給N個點M條邊，求從點N走回點1的最短路
做法：
那就拿來複習Dijkstra吧> <
D[i]表示從起點到i的最短路，初始值設為INF(起點是0)，然後開始bfs&relax
將bfs到的點push進PQ，PQ我也是用edge型態{to, cost}，但裡面其實是存{i.to, D[i.to]}
照cost排序，也就是讓目前距離"最短路徑樹"較近的點優先。
每次皆從距離答案最近的點優先繼續擴展下去，一路到終點中找到的路就是答案，即是Dijkstra的精髓，這是可以證明出來的
在取出時判斷if ( t.cost > D[t.to] )，不同代表他已經被更新過了，已經有找到解了，所以continue;
code:
將bfs到的點push進PQ，PQ我也是用edge型態{to, cost}，但裡面其實是存{i.to, D[i.to]}
照cost排序，也就是讓目前距離"最短路徑樹"較近的點優先。
每次皆從距離答案最近的點優先繼續擴展下去，一路到終點中找到的路就是答案，即是Dijkstra的精髓，這是可以證明出來的
在取出時判斷if ( t.cost > D[t.to] )，不同代表他已經被更新過了，已經有找到解了，所以continue;
code:
沒有留言:
張貼留言