dijkstra演算法的應用

㈠ 關於Dijkstra演算法

樓上正解，你找個圖自己用此演算法實踐一下就知道了，從A點出發，發現離A最近的點是B點，那麼我們就已經認為A到B的最短距離就是AB了，如果有負數，就指不定冒出個C點,AC+CB<AB;或者冒出個DE為很大的負值，AC+CD+DE+EF+FB<AB;等等諸如此類的情況。
簡單說來，你駕車從家出發到某地沿某條路只需經過一個收費站，但是遠在外省某地有個站不但不收你的費，你去了還會給你個千八百萬的歡迎光臨費，你能說你直接沿著這條路去某地是最省費用的？不計時間成本，繞到外省那個給你錢的地方，再繞回到你的目的地，還能賺錢呢。
而且一般權值為負的圖研究也比較少。有些帶負權的圖，某些點間還沒有最小距離呢。中間出個帶某條負權很大的邊的環圈，繞此一圈所經過的距離反而減少了，那就一直在此圈上繞啊繞啊繞到負的足夠大溢出為止。
當然考慮各種自己隨便假設出來的變種問題也是很有趣的。比如說邊帶有多個權值對應多次經過改變的消費，上面的問題有可能變成有解的。話說那個站會後悔，第二次經過它會收回100萬，第三次經過收回250萬，這樣的話你只需要經過一次就夠了，問題也是有解的。再比如說對於多權重圖，從A點出發經過B點到達C點的最短路線，就不是簡單的AB最短路線+BC最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^

㈡ Dijkstra演算法

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。注意該演算法要求圖中不存在負權邊。

設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度含侍仿。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為「起點D到該頂點的距離」（例如，U中頂點A的距離為[D,A]的長度，然後D和A不相鄰，則談棗A的距離為∞）
（2）從U中選出「距離最短的頂點K」，並將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由於上一步談纖中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大於[D,K]+[K,A]的距離）
（4）重復步驟（2）和（3），直到遍歷完所有頂點

https://blog.csdn.net/yalishadaa/article/details/55827681

㈢ dijkstra演算法是什麼

Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。

其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。

不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。

因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。

㈣ 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，改培2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題