search

wylee / Dijkstar

Graphs, Dijkstra, A*, shortest paths, HTTP graph server
MIT License
55 stars 17 forks source link

Doesn't work #3

Closed Vadims06 closed 5 years ago

Vadims06 commented 5 years ago 
graph = Graph()
graph.add_edge(1, 2, {'cost': 10})
graph.add_edge(1, 5, {'cost': 1})
graph.add_edge(1, 6, {'cost': 100})
graph.add_edge(2, 3, {'cost': 1})
graph.add_edge(3, 4, {'cost': 1})
graph.add_edge(3, 5, {'cost': 1})
graph.add_edge(3, 6, {'cost': 100})
graph.add_edge(3, 7, {'cost': 1})
graph.add_edge(4, 3, {'cost': 1})
graph.add_edge(4, 7, {'cost': 1})
graph.add_edge(5, 1, {'cost': 1})
graph.add_edge(5, 3, {'cost': 1})
graph.add_edge(5, 7, {'cost': 1})
graph.add_edge(6, 1, {'cost': 100})
graph.add_edge(6, 3, {'cost': 100})
graph.add_edge(7, 5, {'cost': 1})
graph.add_edge(7, 3, {'cost': 1})
graph.add_edge(7, 4, {'cost': 1})

I run Dijkstra, find BEST path, then remove node from SPT and try to find the SPT without this node. Regarding my topology there is path between 1-5-7-3-4, but this module cannot find this

PathInfo(nodes=[1, 5, 3, 4], edges=[{'cost': 1}, {'cost': 1}, {'cost': 1}], costs=[1, 1, 1], total_cost=3) took 5 from queue [5, 3] pop {5} and became PathInfo(nodes=[1, 2, 3, 4], edges=[{'cost': 10}, {'cost': 1}, {'cost': 1}], costs=[10, 1, 1], total_cost=12) took 3 from queue [5, 3, 2] no backup path without {3, 5}

Vadims06 commented 5 years ago

the error was in topology