Python中Dijkstra的算法 [英] Dijkstra's algorithm in python

问题描述

我正在尝试使用数组在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}

这篇关于Python中Dijkstra的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！