目錄

1）使用狄克斯特拉算法

2）術(shù)語

3）實(shí)現(xiàn)

4）小結(jié)

---

本章內(nèi)容;

• ? ? ? ?介紹加權(quán)圖，提高或降低某些邊的權(quán)重；
• ? ? ? ?介紹狄克斯特拉算法，找出加權(quán)圖中前往X的最短路徑；
• ? ? ? ?介紹圖中的環(huán)，它導(dǎo)致狄克斯特拉算法不管用；

在上一篇博客中，我們找到了從A到B的路徑，這是最短路徑，只有三段，但不一定是最短路徑。

廣度優(yōu)先搜索可以找出段數(shù)最少的路徑，但如果要找出最快的路徑，可使用狄克斯特拉算法。

1）使用狄克斯特拉算法

還是來看一個(gè)例子，如何對下面的圖使用這種算法。圖中每個(gè)數(shù)字表示的是時(shí)間，單位是分鐘。如果使用廣度優(yōu)先搜索算法，將得到下面這條段數(shù)最少的路徑。

狄克斯特拉算法包括4個(gè)步驟：

找出“最便宜”的節(jié)點(diǎn)，即可在最短時(shí)間內(nèi)到達(dá)的節(jié)點(diǎn)。

更新該節(jié)點(diǎn)的鄰居的開銷，其含義稍后介紹。

重復(fù)這個(gè)過程，直到對圖中的每個(gè)幾點(diǎn)都這樣做了。

計(jì)算最短路徑。

第一步：找出最便宜的節(jié)點(diǎn)，你站在起點(diǎn)，不知道該前往節(jié)點(diǎn)A還是節(jié)點(diǎn)B。前往節(jié)點(diǎn)A需要6分鐘，前往節(jié)點(diǎn)B需要2分鐘，由于還不知道前往終點(diǎn)需要多長時(shí)間，因此假設(shè)為無窮大。

? ??

第二步：計(jì)算經(jīng)節(jié)點(diǎn)B前往其各個(gè)鄰居所需的時(shí)間。

對于節(jié)點(diǎn)B的鄰居，如果找到前往它的更短路徑，就更新其開銷。在這里，我們找到了：

前往節(jié)點(diǎn)A的更短路徑（時(shí)間從6分鐘縮短到5分鐘）。

前往終點(diǎn)的更短路徑（時(shí)間從無窮大縮短到7分鐘）。

第三步：重復(fù)！

現(xiàn)在更新節(jié)點(diǎn)A的所有鄰居的開銷。這時(shí)前往終點(diǎn)的時(shí)間縮短到6分鐘。

2）術(shù)語

狄克斯特拉算法用于每條邊都有關(guān)聯(lián)數(shù)字的圖，這些數(shù)字稱為權(quán)重（weight）。

帶權(quán)重的圖稱為加權(quán)圖，不帶權(quán)重的圖稱為非加權(quán)重。

要計(jì)算非加權(quán)圖中的最短路徑，可使用廣度優(yōu)先搜索，要計(jì)算加權(quán)圖中的最短路徑，可使用狄克斯特拉算法。這里需要指出的時(shí)，狄克斯特拉算法只適用與有向無環(huán)圖。

3）實(shí)現(xiàn)

下面來看看如何用代碼來實(shí)現(xiàn)狄克斯特拉算法。要解決這個(gè)問題，需要用到散列表。

隨著算法的進(jìn)行，不斷地更新散列表COSTS和PARENTS。Python實(shí)現(xiàn)代碼如下：

# the graph graph = {} graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2graph["a"] = {} graph["a"]["fin"] = 1graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5graph["fin"] = {}# the costs table infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity# the parents table parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = Noneprocessed = []def find_lowest_cost_node(costs):lowest_cost = float("inf")lowest_cost_node = None# Go through each node.for node in costs:cost = costs[node]# If it's the lowest cost so far and hasn't been processed yet...if cost < lowest_cost and node not in processed:# ... set it as the new lowest-cost node.lowest_cost = costlowest_cost_node = nodereturn lowest_cost_node# Find the lowest-cost node that you haven't processed yet. node = find_lowest_cost_node(costs) # If you've processed all the nodes, this while loop is done. while node is not None:cost = costs[node]# Go through all the neighbors of this node.neighbors = graph[node]for n in neighbors.keys():new_cost = cost + neighbors[n]# If it's cheaper to get to this neighbor by going through this node...if costs[n] > new_cost:# ... update the cost for this node.costs[n] = new_cost# This node becomes the new parent for this neighbor.parents[n] = node# Mark the node as processed.processed.append(node)# Find the next node to process, and loop.node = find_lowest_cost_node(costs)print "Cost from the start to each node:" print costs

4）小結(jié)

廣度優(yōu)先搜索用于在非加權(quán)圖中查找最短路徑。

狄克斯特拉算法用于在加權(quán)圖中查找最短路徑。

僅當(dāng)權(quán)重為正時(shí)狄克斯特拉算法才管用。

如果圖中包含負(fù)權(quán)邊，請使用貝爾曼---福德算法。

總結(jié)

以上是生活随笔為你收集整理的图解算法学习笔记（七）：狄克斯特拉算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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