Dijkstra 算法不起作用并给出错误的距离

Question

我正在实施 Dijkstra 算法来查找图中两个节点之间的最短路径，虽然我看到代码是正确的，但它不适用于大多数示例，我不知道为什么，

我的代码：

import networkx as nx
import math

def Dijkstra(graph, source, goal):
    Distance = {}
    Predecessor = {}
    Q = []
    visited_vertices = set()
    for V in graph.nodes:
        Distance[V] = 0
        Q.append(V)
    Distance[source] = 0
    while Q:
        node_u = find_minimum(Q,Distance)
        Q.remove(node_u)
        visited_vertices.add(node_u)
        for node_v in graph.neighbors(node_u):
            if node_v in visited_vertices:
                continue
            weight_u_v = get_weight(graph, node_u, node_v)
            if Distance[node_u] + weight_u_v < Distance[node_v]:
                Distance[node_v] = Distance[node_u] + weight_u_v
                Predecessor[node_v] = node_u
    return Distance

def find_minimum(Q, Distance):
    minimum = math.inf
    minimum_index = None
    for i in range(len(Q)):
        if Distance[Q[i]] < minimum:
            minimum = Distance[Q[i]]
            minimum_index = i
    return Q[minimum_index]


def get_weight(graph, node_u, node_v):
    return graph.get_edge_data(node_u,node_v)['weight']

def main():
    graph = nx.Graph()
    graph.add_node('V0')
    graph.add_node('V1')
    graph.add_node('V2')
    graph.add_node('V3')
    graph.add_node('V4')
    edges = []
    edges.append(('V0','V1',10))
    edges.append(('V1','V2',5))
    edges.append(('V2','V3',-25))
    edges.append(('V0','V3',3))
    edges.append(('V3','V4',8))
    graph.add_weighted_edges_from(edges)


    d = Dijkstra(graph,'V4','V2')
    print(d)

if __name__ == '__main__':
    main()

你可以复制它并尝试运行它，对于V4到V2输出是

{'V0': 0, 'V1': 0, 'V2': 0, 'V3': -25, 'V4': -17}

它应该在哪里

{'V0': -2, 'V1': -12, 'V2': -17, 'V3': 8, 'V4': 0}

我真的不知道为什么会这样。

Answer 1

首先，Dijkstra algorithm cannot handle negative weights on edges, you should use Bellman-Ford算法来实现它。

Dijkstra 算法不起作用并给出错误的距离

Dijkstra algorithm is not working and gives wrong distances

python

algorithm

graph

graph-algorithm

shortest-path