最短路徑

算法特點：

迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。

算法思路：

Dijkstra算法采用的是一種貪心的策略，聲明一個數(shù)組dis來保存源點到各個頂點的最短距離和一個保存已經(jīng)找到了最短路徑的頂點的集合：T，初始時，原點 s 的路徑權(quán)重被賦為 0 (dis[s] = 0)。若對于頂點 s 存在能直接到達(dá)的邊(s,m)，則把dis[m]設(shè)為w(s, m),同時把所有其他(s不能直接到達(dá)的)頂點的路徑長度設(shè)為無窮大。初始時，集合T只有頂點s。

然后，從dis數(shù)組選擇最小值，則該值就是源點s到該值對應(yīng)的頂點的最短路徑，并且把該點加入到T中，OK，此時完成一個頂點，

然后，我們需要看看新加入的頂點是否可以到達(dá)其他頂點并且看看通過該頂點到達(dá)其他點的路徑長度是否比源點直接到達(dá)短，如果是，那么就替換這些頂點在dis中的值。

然后，又從dis中找出最小值，重復(fù)上述動作，直到T中包含了圖的所有頂點。

為什么dijkstra算法處理不了帶有負(fù)權(quán)值的邊的圖？

下面說法有點道理但也有漏洞，供參考：

例子：

思考題：Dijkstra可以求帶權(quán)無向圖最短路徑么

可以

總結(jié)

以上是生活随笔為你收集整理的数据结构最短路径例题_编程小白暑期进阶笔记45-C语言数据结构与算法最短路径和dijkstra算法...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。