Path search with undefined start and end nodes

There are algorithms to determine the shortest path between two nodes, or the widest path, or paths that are optimal in some other way. From my (admittedly limited) exposure to graph theory and network science, however, all path search algorithms seem to require a start and end node to be selected.

Are there any algorithms that search through paths of any length, beginning and ending on any nodes, that optimise some specified metric?

Jeff, there are indeed such algorithms: All Pairs Shortest Paths algorithms. If you want to really get into it, read the classic CLRS algorithms text, or my summary of the relevant chapter here: http://www2.hawaii.edu/~suthers/courses/ics311f20/Notes/Topic-19.html

When there are no weights on the edges (or the “specified metric” is simply 1 on every edge), simple breadth first search suffices. But when you have weights it gets more complex. In that case, one might intuit that specifying the start and end nodes would make an algorithm faster, but this is not true for the end node. In order to ensure we are reaching the end node via the shortest path we need to be sure we could not have found a shorter path by going via some other node, so ensuring an optimal solution for the single-source single-target problem requires solving the single-source all-target problem! But solving shortest paths for all start nodes does take longer than for a single start node, as discussed in the above notes.

1 Like

Hi Dan, thank you very much for your help! This is exactly the kind of guidance I was hoping for.

For my specific application, I want to find the ‘strongest’ path rather than the shortest path, with path strength determined by a custom metric. It sounds as though an All Pairs Shortest Path algorithm will optimise whatever objective function I choose, I just need to replace the shortest path objective with my own metric. Would that be correct? And I believe my graphs will be sparse, in which case the Floyd-Warshall algorithm is the most appropriate one that I should seek to adapt for my application?