Dijkstra algorithm is not working and gives wrong distances

Question

I'm implementing Dijkstra algorithm to find the shortest path between two nodes in a graph, although I see the code is currect it does not work for most of the examples and I don't know why,

my code:

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()

you can copy it and try to run it, for V4 to V2 the output is

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

where it should be

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

and I really don't know why this is happening.

you add nodes to the `visited_vertices` but you never **read** what nodes have been visited (and treat them as handled). — hiro protagonist, Dec 03 '20 at 15:35
Specifying where you think it is in the infinite loop would be helpful. — Tom Myddeltyn, Dec 03 '20 at 15:42
@hiroprotagonist thank you! I don't know how that slipped, althought now i'm facing another problem — SAAD, Dec 03 '20 at 15:48
You have to initialize distance array for all vertexes except `source` as Infinities, not zeroes. And during the algorithm you will improve distances. — Iaroslav Sviridov, Dec 03 '20 at 15:51
Here I think this explains it well. https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges — Tom Myddeltyn, Dec 03 '20 at 17:03

Iaroslav Sviridov · Accepted Answer · 2020-12-03T16:02:13.513

0

First of all, Dijkstra algorithm cannot handle negative weights on edges, you should use Bellman-Ford algorithm to achieve it.

edited Dec 03 '20 at 16:02

answered Dec 03 '20 at 15:56

Iaroslav Sviridov

128
7

really? I thought it was the other way around, but I tried previously implementing bellmanford and it has only a way of detecting a negative edge but not give the shortest path in a negative edges graph, do you know which algorithm can give me a the shortest path in a situation like this if one exist? and thanks for helping! I really appreciate it. – SAAD Dec 03 '20 at 16:02
@SAAD as I said in answer, you should use Bellman-Ford algorithm, if it doesn't work correctly, it means you made a mistake in its implementation somewhere. Look at the attached wikipedia link for better understanding. – Iaroslav Sviridov Dec 03 '20 at 16:14

Dijkstra algorithm is not working and gives wrong distances

1 Answers1