最短路径算法的实现（dijskstra）：Python

dijskstra最短路径算法步骤：

输入：图G=（V(G),E(G)）有一个源顶点S和一个汇顶点t，以及对所有的边ij属于E（G）的非负边长出c_ij。

输出：G从s到t的最短路径的长度。

第0步：从对每个顶点做临时标记L开始，做法如下：L（s）=0,且对除s外所有的顶点L（i）=∞。

第1步：找带有最小临时标记的顶点（如果有结，随机地取一个），使得该标记变成永久标记，意该标记永久不再改变。

第2步：对没有永久标记但是又与带永久标记的顶点相邻的顶点j，按如下方法计算一个新的临时标记：L（j）=min（L（i）+c_ij），求最小是对所有带永久标记的顶点i做的，重复1和2，知道所有的顶点都打上永久标记。

时间复杂度：O（n^2）

python代码如下

 __author__='wym'

 #coding=cp936

 class Algorithm():

     point_list=[]

     edge_list=[]

     def dijkstra(self,start_point,point_list,edge_list):

         '''

         @point为起始点

         @point_list为顶点列表

         @edge_list为边列表

         '''

         #列表点

         temp_point=[]

         #起始点，在列表点中的位置

         point_index=point_list.index(start_point)

         #初始点到其余各点的距离字典

         dis_dic=dict()

         #边列表的首端点列表

         temp_edge=[]

         #距离初始化

         dis_list=['inf']*len(point_list)

         temp_point.append(start_point)

         dis_list[point_index]=0

         for i in range(len(point_list)):

             dis_dic.setdefault(point_list[i],dis_list[i])

         for i in range(len(edge_list)):

             temp_edge.append(edge_list[i][0])

         point=start_point

         #依次遍历加入最小距离的点，并更新原列表中点的距离

         while len(temp_point)<len(point_list):

             index=self.find_index(point,temp_edge,edge_list,temp_point)

             #判断是否走的通

             if len(index)>0:

                 value=edge_list[index[0]][2]

                 add_index=index[0]

                 for i in index:

                     if edge_list[i][0] in dis_dic:

                         dis_dic[edge_list[i][1]]=min(float(edge_list[i][2])+float(dis_dic[point]),float(dis_dic[edge_list[i][1]]))

                     if value>edge_list[i][2]:

                         value=edge_list[i][2]

                         add_index=i

                 temp_point.append(edge_list[add_index][1])

                 point=edge_list[add_index][1]

             else:

                 point=in_list[in_list.index(point)-1]

         print dis_dic

         return dis_dic

     def find_index(self,point,temp_edge,edge_list,temp_point):

         '''

         @point:遍历点基准点

         @temp_edge：边列表的首端点列表

         @edge_list：边权列表

         @temp_point：列表点

         @返回边权列表列表索引

         '''

         #寻找点的索引，并去除已在列表中的点

         index=[]

         for i in range(len(temp_edge)):

             if point==temp_edge[i] and edge_list[i][1] not in temp_point:

                 index.append(i)

         return index

 if __name__=="__main__":

     print '请输入无向图的顶点'

     point_list=input()

     print '请输入无向图的边'

     edge_list=list(input())

     print '请输入各边长度'

     for i in range(len(edge_list)):

         print '顶点'+str(edge_list[i][0])+'顶点'+str(edge_list[i][1])+'的长度为：'

         length=[input("长度为：")]

         edge_list[i]+=length

         edge_list.append([edge_list[i][1],edge_list[i][0],length[0]])

     while True:

         print '请输入起始点'

         start_point=input("start_point=")

         if start_point in point_list:

             obj=Algorithm()

             obj.dijkstra(start_point,point_list,edge_list)

             break

         else:

             print '该点不在图中，请重新输入:'

             continue

运行结果：

请输入无向图的顶点
1,2,3,4,5,6
请输入无向图的边
[1,6],[1,3],[1,2],[2,3],[3,6],[2,4],[3,4],[4,5],[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}

巴特西

最短路径算法的实现（dijskstra）：Python

最新文章

热门文章