search

wylee / Dijkstar

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

Getting all nodes' shortest path cost #4

Open MicalKarl opened 5 years ago

MicalKarl commented 5 years ago

Since dijkstar algorithm can get a node to another node's shortest path and the node to all other nodes' shortest path. But the project only shows the shortest path from node u to node v, the remaining information of the shortest paths from node u to all other nodes can not be retrieved, some usage of this remaining information can be used! Can you add the interface of getting node u to all other nodes' shortest paths? I'm looking for your rely!

wylee commented 5 years ago

Finding paths to all nodes reachable from a given start node isn't well-tested because I haven't had a need for that functionality myself. In theory, you should be able to repeatedly call extract_shortest_path_from_predecessor_list() with the predecessor map returned from single_source_shortest_paths() and each reachable destination node.

Thinking about it now, I suppose the problem is knowing what all the destination nodes are. It should be possible to extract them from the predecessor map, but that's currently not very convenient. I might look into adding a find_all_paths function if I find some time, but in the meantime I would happily accept a patch that includes tests.