在解決最短路徑優(yōu)化問題中，Dijkstra算法有哪些優(yōu).缺點？優(yōu)點：算法簡潔，能得到最優(yōu)解，缺點：效率低（特別是有時不需要最優(yōu)解），運算空間大因為Dijkstra貪心，他總是找到一個離源點最近的點（D

在解決最短路徑優(yōu)化問題中，Dijkstra算法有哪些優(yōu).缺點？

優(yōu)點：算法簡潔，能得到最優(yōu)解，缺點：效率低（特別是有時不需要最優(yōu)解），運算空間大

因為Dijkstra貪心，他總是找到一個離源點最近的點（Dmin），然后將距離確定為從該點到源點的最短路徑（d[i]<--Dmin）；但如果存在負權(quán)重邊，則可以首先傳遞一個不最接近源點的次優(yōu)勢（Dmin”），然后通過負權(quán)邊L（L<0）使路徑之和變?。―min”），這樣Dijkstra就會丟失。

例如，n=3，鄰接矩陣：

0，3，4

3，0，-2

4，-2，0

使用Dijkstra得到d[1，2]=3，實際上，d[1，2]=2，這使得路徑通過1-3-2遞減。

迪杰斯特拉算法為什么不能有負權(quán)邊？

計算機算法太多了。記得我在學(xué)校的時候，老師說：程序=算法數(shù)據(jù)結(jié)構(gòu)，算法是構(gòu)建軟件的基礎(chǔ)。R比較常見的算法有：排序，有n種排序算法，復(fù)雜度最低的似乎是o（nlogn）；在長串中尋找子串的算法有KMP算法；在地圖中尋找最短路徑的算法有Dijkstra算法a*算法；很多關(guān)于樹的算法，如平衡二叉樹；在有序數(shù)組中求數(shù)的半搜索算法；計算表達式的解析算法。。。R太多了?？梢哉f，我們看到的每一個軟件背后都有無數(shù)的算法可以高效運行