求网站开发客户,网上申报食品经营许可证流程,上海it公司有哪些,手机app下载平台哪个好dijskstra最短路径算法步骤#xff1a;输入#xff1a;图G(V(G),E(G))有一个源顶点S和一个汇顶点t#xff0c;以及对所有的边ij属于E(G)的非负边长出cij。输出#xff1a;G从s到t的最短路径的长度。第0步#xff1a;从对每个顶点做临时标记L开始#xff0c;做法如下…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__wym2 #codingcp9363 classAlgorithm():4 point_list[]5 edge_list[]6 defdijkstra(self,start_point,point_list,edge_list):7 8 point为起始点9 point_list为顶点列表10 edge_list为边列表11 12 #列表点13 temp_point[]14 #起始点在列表点中的位置15 point_indexpoint_list.index(start_point)16 #初始点到其余各点的距离字典17 dis_dicdict()18 #边列表的首端点列表19 temp_edge[]20 #距离初始化21 dis_list[inf]*len(point_list)22 temp_point.append(start_point)23 dis_list[point_index]024 for i inrange(len(point_list)):25 dis_dic.setdefault(point_list[i],dis_list[i])26 for i inrange(len(edge_list)):27 temp_edge.append(edge_list[i][0])28 pointstart_point29 #依次遍历加入最小距离的点并更新原列表中点的距离30 while len(temp_point)33 if len(index)0:34 valueedge_list[index[0]][2]35 add_indexindex[0]36 for i inindex:37 if edge_list[i][0] indis_dic:38 dis_dic[edge_list[i][1]]min(float(edge_list[i][2])float(dis_dic[point]),float(dis_dic[edge_list[i][1]]))39 if valueedge_list[i][2]:40 valueedge_list[i][2]41 add_indexi42 temp_point.append(edge_list[add_index][1])43 pointedge_list[add_index][1]44 else:45 pointin_list[in_list.index(point)-1]46 printdis_dic47 returndis_dic48 deffind_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 inrange(len(temp_edge)):59 if pointtemp_edge[i] and edge_list[i][1] not intemp_point:60 index.append(i)61 returnindex6263 if __name____main__:64 print 请输入无向图的顶点65 point_listinput()66 print 请输入无向图的边67 edge_listlist(input())68 print 请输入各边长度69 for i inrange(len(edge_list)):70 print 顶点str(edge_list[i][0])顶点str(edge_list[i][1])的长度为71 length[input(长度为)]72 edge_list[i]length73 edge_list.append([edge_list[i][1],edge_list[i][0],length[0]])74 whileTrue:75 print 请输入起始点76 start_pointinput(start_point)77 if start_point inpoint_list:78 objAlgorithm()79 obj.dijkstra(start_point,point_list,edge_list)80 break81 else:82 print 该点不在图中请重新输入:83 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_point1{1: 0, 2: 7.0, 3: 9.0, 4: 20.0, 5: 20.0, 6: 11.0}
