最短路径算法的实现（dijskstra）：Python
dijskstra最短路径算法步骤：输入：图G=（V(G),E(G)）有一个源顶点S和一个汇顶点t，以及对所有的边ij属于E（G）的非负边长出cij。
输出：G从s到t的最短路径的长度。
第0步：从对每个顶点做临时标记L开始，做法如下：L（s）=0,且对除s外所有的顶点L（i）=∞。
第1步：找带有最小临时标记的顶点（如果有结，随机地取一个），使得该标记变成永久标记，意该标记永久不再改变。
第2步：对没有永久标记但是又与带永久标记的顶点相邻的顶点j，按如下方法计算一个新的临时标记：L（j）=min（L（i）+cij），求最小是对所有带永久标记的顶点i做的，重复1和2，知道所有的顶点都打上永久标记。
时间复杂度：O（n^2）
python代码如下
1 __author__='wym'
2 #coding=cp936
3 class Algorithm():
4 point_list=[]
5 edge_list=[]
6 def dijkstra(self,start_point,point_list,edge_list):
7 '''
8 @point为起始点
9 @point_list为顶点列表
10 @edge_list为边列表
11 '''
12 #列表点
13 temp_point=[]
14 #起始点，在列表点中的位置
15 point_index=point_list.index(start_point)
16 #初始点到其余各点的距离字典
17 dis_dic=dict()
18 #边列表的首端点列表
19 temp_edge=[]
20 #距离初始化
21 dis_list=['inf']*len(point_list)
22 temp_point.append(start_point)
23 dis_list=0
24 for i in range(len(point_list)):
25 dis_dic.setdefault(point_list,dis_list)
26 for i in range(len(edge_list)):
27 temp_edge.append(edge_list)
28 point=start_point
29 #依次遍历加入最小距离的点，并更新原列表中点的距离
30 while len(temp_point)<len(point_list):
31 index=self.find_index(point,temp_edge,edge_list,temp_point)
32 #判断是否走的通
33 if len(index)>0:
34 value=edge_list]
35 add_index=index
36 for i in index:
37 if edge_list in dis_dic:
38 dis_dic]=min(float(edge_list)+float(dis_dic),float(dis_dic]))
39 if value>edge_list:
40 value=edge_list
41 add_index=i
42 temp_point.append(edge_list)
43 point=edge_list
44 else:
45 point=in_list
46 print dis_dic
47 return dis_dic
48 def find_index(self,point,temp_edge,edge_list,temp_point):
49 '''
50 @point:遍历点基准点
51 @temp_edge：边列表的首端点列表
52 @edge_list：边权列表
53 @temp_point：列表点
54 @返回边权列表列表索引
55 '''
56 #寻找点的索引，并去除已在列表中的点
57 index=[]
58 for i in range(len(temp_edge)):
59 if point==temp_edge and edge_list not in temp_point:
60 index.append(i)
61 return index
62
63 if __name__=="__main__":
64 print '请输入无向图的顶点'
65 point_list=input()
66 print '请输入无向图的边'
67 edge_list=list(input())
68 print '请输入各边长度'
69 for i in range(len(edge_list)):
70 print '顶点'+str(edge_list)+'顶点'+str(edge_list)+'的长度为：'
71 length=
72 edge_list+=length
73 edge_list.append(,edge_list,length])
74 while True:
75 print '请输入起始点'
76 start_point=input("start_point=")
77 if start_point in point_list:
78 obj=Algorithm()
79 obj.dijkstra(start_point,point_list,edge_list)
80 break
81 else:
82 print '该点不在图中，请重新输入:'
83 continue
运行结果：
请输入无向图的顶点
1,2,3,4,5,6
请输入无向图的边
,,,,,,,,
请输入各边长度
顶点1顶点6的长度为：
长度为：14
顶点1顶点3的长度为：
长度为：9
顶点1顶点2的长度为：
长度为：7
顶点2顶点3的长度为：
长度为：10
顶点3顶点6的长度为：
长度为：2
顶点2顶点4的长度为：
长度为：15
顶点3顶点4的长度为：
长度为：11
顶点4顶点5的长度为：
长度为：6
顶点5顶点6的长度为：
长度为：9
请输入起始点
start_point=1
{1: 0, 2: 7.0, 3: 9.0, 4: 20.0, 5: 20.0, 6: 11.0}
页:
[1]