没事撸点算法——dijkstra算法（python）

数据结构地提出是为了更好地解决数据存储问题，图数据结构的提出是为了解决生活中的复杂网络问题。

在Python中，图的表示方式一般使用字典以及列表完成。

#使用字典列表展现图
graph={
       1:{2:1,3:12},
       2:{3:9,4:3},
       3:{5:5},
       4:{3:4,5:13,6:15},
       5:{6:4},
       6:{6:0}
       }

Dijkstra算法一般是用于解决求解最短路径问题，属于盲目搜索算法。

原理：不断求解起始节点到其他节点的最短路径成本。

First：

引入cost字典，表示对于起始点到每一个其他节点的成本。eg:cost[2]=1。表示起始点（这里设定为节点1）到节点2的成本需要1。

引入visted列表，记录已访问的节点。eg:起始visted=[1];

引入Parents字典，记录已求解最短路径节点的前一个节点。eg:假设至3节点的最短路径为1-2-4-3，则parents[3]=4;

Second:算法流程（以上面的网络图为例）

cost初始值为1节点到各个节点的成本

1	2	3	4	5	6
0	1	12	999（无穷）	999（无穷）	999（无穷）

可以得出1-2的最短路径成本即为1。因为1节点到2节点仅有一条路径最短，如果1节点先到其他节点之后再返回2节点，必然成本大于1，所以1-2为2节点的最低成本路径。此时将2节点放置visted中。

接下来，由于节点2已经解出1-2的最短路径，计算2节点的出度（2-3，2-4）由1-2-3和1-2-4的成本分别为10、4小于之前的成本12、999，对cost字典进行更新。

1	2	3	4	5	6
0	1	10	4	999	999

此时，cost成本最小的为节点4，最短路径为1-2-4，将4放入visted列表中，记录parents[4]=2。

再看4的出度，对cost列表进行更新，寻找成本最小节点，记入visted列表中，同时记录当前最短路径节点的前一个节点，知道所有节点全部被访问，即全部进入visted列表中，结束算法。

全部代码：

# -*- coding: utf-8 -*-
"""
Created on Tue Oct 30 08:46:14 2018

@author: 24367
"""
# find the shortest node(not visted) to add in the list(visted)
def find_shortest_node(cost):
        minDist=999
        node=None
        for item in cost.keys():
            if (cost[item]<minDist)&(item not in visted):
                minDist=cost[item]
                node=item
        return node
        

#Create Graph for the route plan
graph={
       1:{2:1,3:12},
       2:{3:9,4:3},
       3:{5:5},
       4:{3:4,5:13,6:15},
       5:{6:4},
       6:{6:0}
       }
#记录初始权值
cost={1:0,2:1,3:12,4:999,5:999,6:999}
#记录当前最短路径的前一个节点
parents={1:None,2:1,3:2,4:2,5:3,6:5}
#记录已经访问过的节点
visted=[1]
node=find_shortest_node(cost)
while (node):
    for i in graph[node]:
        newCost=cost[node]+graph[node][i];
        if(newCost<cost[i]):
            #更新cost权值以及记录最短路径前节点
            cost[i]=newCost
            parents[i]=node
    visted.append(node)#将最短路径节点添加至已访问列表中
    node=find_shortest_node(cost)
#输出最短路径
parent=parents[6]
while(parent):
    print(parent)
    parent=parents[parent]

没事撸点算法——dijkstra算法（python）

相关推荐