三、最短路徑之Dijkstra算法

1.Dijkstra算法

1.1算法介紹

1.2算法原理

1.3算法過程

1.4算法示例

從節點1出發到圖中其餘節點的最短路徑分别是：

    2—8,3—15,4--20,5—13,6--18

程式：

說明：這裡假設邊的權重最大不超過100，以此代替無窮大；利用s和s1分别儲存兩個不同的點集合，d中儲存l數組

import networkx as nx
def Dijkstra(i,G=nx.Graph):
    s=[]
    s1=[]
    d=[]
    s.append(i)
    d.append(0)
    for node in G.nodes():
        if node != i:
            s1.append(node)
            d.append(100)
    while s1:
        u_item=s[len(s)-1]
        for node in s1:
            if G.has_edge(u_item,node):
                if d[node-1]>G.get_edge_data(u_item,node)['weight']+d[u_item-1]:
                    d[node-1]=G.get_edge_data(u_item,node)['weight']+d[u_item-1]
        index=0
        if len(s1)==1:
            index=0
        else:
            i=1
            while i<len(s1):
                if d[s1[i]-1]<d[s1[index]-1]:
                    index=i
                i=i+1
        s.append(s1[index])
        del s1[index]
    print d
G=nx.Graph()
G.add_weighted_edges_from([(1,2,8),(1,3,16),(1,5,13),(2,3,7),(2,4,17),(2,5,11),(2,6,10),(3,4,5),(4,5,14),(4,6,6)])
Dijkstra(1,G)
           

結果