Python中Dijkstra的算法

本文介绍了Python中Dijkstra的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试使用数组在python中实现Dijkstra的算法。这是我的实现。

def提取（Q，w）：m = 0 minimum = w [0] i在范围（len（w））中的：如果w [i] ＜最小值：最小值= w [i] m = i return m，Q [m] def dijkstra（G，s，t ='B'）： Q = [s] p = {s：None} w = [0] d = {} for i in G：d [i] = float（'inf'） Q.append（i） w.append （d [i]）d [s] = 0 S = [] n = len（Q）而Q：u = extract（Q，w） [1] S.append（u）＃w.remove（extract（Q，d，w）[0]） Q.remove（u） for v在G [u]中：如果d [v]> = d [u] + G [u] [v]：b：d [v] = d [u] + G [u] [v ] p [v] = u return d，p B ='B' A ='A' D ='D' G ='G' E ='E' C ='C' F ='F' G = { B：{A：5，D：1，G：2}，A：{B：5，D：3，E：12，F：5}，D​​：{B：1，G：1，E：1 ，A：3}，G：{B：2，D：1，C：2}，C：{G：2，E：1，F：16}，E：{A：12，D：1，C ：1，F：2}，F：{A：5，E：2，C：16}} 打印假定起始顶点为B： 打印最短距离，dijkstra （G，B）[0] 打印父母，dijkstra（G，B）[1]

我希望答案是：

假设起始顶点为B：最短距离{'A'：4，'C'：4，'B'：0，'E'：2，'D'：1，'G'：2，'F'：4} 父母{' A'：'D'，'C'：'G'，'B'：无，'E'：'D'，'D'：'B'，'G'：'D'，'F'：' E'}

不过，我得到的答案是：

假设起始顶点为B：最短距离{'A'：4，'C'：4，'B'：0，' E'：2，'D'：1，'G'：2，'F'：10} 父母{'A'：'D'，'C'：'G'，'B'：无， E： D， D： B， G： D， F： A}。

对于节点F，程序给出了错误的答案。有人可以告诉我为什么吗？

解决方案

正如其他人指出的那样，由于未使用可理解的变量名，几乎是不可能的调试代码。

在有关Dijkstra算法的Wiki文章之后，可以按照以下方式（以及百万种其他方式）实现该代码：

nodes =（'A'，'B'，'C'，'D'，'E'，'F'，'G'）距离= {'B'：{'A'：5，'D'：1，'G'：2}，'A'：{'B'：5，' D'：3，'E'：12，'F'：5}，'D'：{'B'：1，'G'：1，'E'：1，'A'：3 }，'G'：{'B'：2，'D'：1，'C'：2}，'C'：{'G'：2，'E'：1 ，'F'：16}，'E'：{'A'：12，'D'：1，'C'：1，'F'：2}，'F'： {'A'：5，'E'：2，'C'：16}}} 未被访问= {node：节点中的节点无}}＃使用无作为+ inf 已访问= {} current ='B' currentDistance = 0 未被访问[current] = currentDistance 而True：邻居为，距离为距离[当前] .item s（）：（如果邻居未访问）：继续 newDistance = currentDistance +距离（如果未访问[neighbour]为无或未访问[neighbour]） newDistance：未访问[邻居] = newDistance 已访问[当前] = currentDistance del未访问[当前] （如果未访问）：break 候选= [node for node在unvisited.items（）中，如果node [1]] current，currentDistance = sorted（candidates，key = lambda x：x [1]）[0] print（visited）

此代码比必要的更为冗长，我希望将您的代码与我的代码进行比较，以发现一些差异。 / p>

结果为：

{'E'：2，' D'：1，'G'：2，'F'：4，'A'：4，'C'：3，'B'：0}

I am trying to implement Dijkstra's algorithm in python using arrays. This is my implementation.

def extract(Q, w): m=0 minimum=w[0] for i in range(len(w)): if w[i]<minimum: minimum=w[i] m=i return m, Q[m] def dijkstra(G, s, t='B'): Q=[s] p={s:None} w=[0] d={} for i in G: d[i]=float('inf') Q.append(i) w.append(d[i]) d[s]=0 S=[] n=len(Q) while Q: u=extract(Q,w)[1] S.append(u) #w.remove(extract(Q, d, w)[0]) Q.remove(u) for v in G[u]: if d[v]>=d[u]+G[u][v]: d[v]=d[u]+G[u][v] p[v]=u return d, p B='B' A='A' D='D' G='G' E='E' C='C' F='F' G={B:{A:5, D:1, G:2}, A:{B:5, D:3, E:12, F:5}, D:{B:1, G:1, E:1, A:3}, G:{B:2, D:1, C:2}, C:{G:2, E:1, F:16}, E:{A:12, D:1, C:1, F:2}, F:{A:5, E:2, C:16}} print "Assuming the start vertex to be B:" print "Shortest distances", dijkstra(G, B)[0] print "Parents", dijkstra(G, B)[1]

I expect the answer to be:

Assuming the start vertex to be B: Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 4} Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'E'}

However, the answer that I get is this:

Assuming the start vertex to be B: Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 10} Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'A'}.

For the node F, the program gives the incorrect answer. Can someone please tell me why?

解决方案

As others have pointed out, due to not using understandable variable names, it is almost impossible to debug your code.

Following the wiki article about Dijkstra's algorithm, one can implement it along these lines (and in a million other manners):

nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G') distances = { 'B': {'A': 5, 'D': 1, 'G': 2}, 'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5}, 'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3}, 'G': {'B': 2, 'D': 1, 'C': 2}, 'C': {'G': 2, 'E': 1, 'F': 16}, 'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2}, 'F': {'A': 5, 'E': 2, 'C': 16}} unvisited = {node: None for node in nodes} #using None as +inf visited = {} current = 'B' currentDistance = 0 unvisited[current] = currentDistance while True: for neighbour, distance in distances[current].items(): if neighbour not in unvisited: continue newDistance = currentDistance + distance if unvisited[neighbour] is None or unvisited[neighbour] > newDistance: unvisited[neighbour] = newDistance visited[current] = currentDistance del unvisited[current] if not unvisited: break candidates = [node for node in unvisited.items() if node[1]] current, currentDistance = sorted(candidates, key = lambda x: x[1])[0] print(visited)

This code is more verbous than necessary and I hope comparing your code with mine you might spot some differences.

The result is:

{'E': 2, 'D': 1, 'G': 2, 'F': 4, 'A': 4, 'C': 3, 'B': 0}