Blog - Hacking Shortest Paths: Solve Harder Problems by Tweaking Graphs

Blog comments
1

Many real-world shortest path problems include constraints that classic algorithms don’t directly handle. NetworkX provides robust, optimized implementations of algorithms like Dijkstra’s, Bellman-Ford, and A*. But what if your problem doesn’t fit the classic shortest path formulation?

This is a companion discussion topic for the original entry at https://blog.scientific-python.org/networkx/hacking-shortest-paths
2

Thanks, Alejandro, I really enjoyed reading your post! It’s fun, thinking about all the possibilities opened up when introducing state copies. It also reminded me of some of the fun tricks we get to play in scikit-image with cost functions in MCP.

I’m curious whether the NetworkX team has discussed the Duan et al. algorithm that was published in June?

4

Thanks Stefan!

Cool to see those graphs algorithms in scikit-image. That cut_threshold function should be a bit faster now with the Networkx 3.6 release!

Regarding Duan et al. I have yet to implement it myself. So far I haven’t seen any implementation that beats Dijkstra’s. The ones that claim so are comparing it against suboptimal implementations.