search

wylee / Dijkstar

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

Add "cost to here" to predecessors and PathInfo? #12

Open wylee opened 5 years ago

wylee commented 5 years ago

Change predecessors[v] = (u, e, cost_of_e) to predecessors[v] = (u, e, cost_of_e, cost_of_s_to_u_plus_cost_of_e) in single_source_shortest_paths(), add a corresponding field to PathInfo, and update extract_shortest_path_from_predecessor_list().

I'm not sure off the top of my head what the use cases for this might be, but I saw that someone created a fork to replace cost_of_e with cost_of_s_to_u_plus_cost_of_e, so it's worth considering.

wylee commented 5 years ago

As this is just sum(info.costs[:i]), it doesn't seem super useful except as a convenience. It would change the API (the return value of find_path() in particular), so it would have to be added to v3. I'm thinking it doesn't seem worth the effort.