Python tutorial 26| Dijkstra

前言

今天要來講講這個最短路徑演算法是什麼。

原理

圖源： https://iter01.com/508741.html

我們可以簡單來看，我們要從A到F，但是要用最少的路徑數字來到F，這樣講有點不清楚我們可以舉例來講A~B要10點數，A~D要4點數，不同通向的地方會有不同點數總合來就是要有多少就多好。

程式

def dijkstra(graph, start):
    visited = []
    index = start
    nodes = dict((i, INF) for i in graph)
    nodes[start] = 0
while len(visited) < len(graph):
        visited.append(index)
        for i in graph[index]:
            new_cost = nodes[index] + graph[index][i]
            if new_cost < nodes[i]:
                nodes[i] = new_cost
next = INF
        for n in nodes:
            if n in visited:
                continue
            if nodes[n] < next:
                next = nodes[n]
                index = n
    return nodes
INF = 9999
graph = {'A':{'A':0, 'B':2, 'C':4},
         'B':{'B':0, 'C':7, 'E':6},
         'C':{'C':0, 'D':6, 'E':2},
         'D':{'D':0, 'E':8, 'G':4},
         'E':{'E':0, 'G':2,},
         'G':{'G':0}
        }
rtn = dijkstra(graph, 'A')
print(rtn)

總結

我累了