在解決最短路徑優(yōu)化問題中，Dijkstra算法有哪些優(yōu).缺點(diǎn)？?jī)?yōu)點(diǎn)：算法簡(jiǎn)潔，能得到最優(yōu)解，缺點(diǎn)：效率低（特別是有時(shí)不需要最優(yōu)解），運(yùn)算空間大因?yàn)镈ijkstra貪心，他總是找到一個(gè)離源點(diǎn)最近的點(diǎn)（D

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

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

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

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

0，3，4

3，0，-2

4，-2，0

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

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

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