Find the shortest Path between two nodes (vertices)
Solution 1
I'm not sure if you need a path between every pair of nodes or between two particular nodes. Since someone has already given an answer addressing the former, I will address the latter.
If you don't have any prior knowledge about the graph (if you do, you can use a heuristic-based search such as A*) then you should use a breadth-first search.
Solution 2
Dijkstra's algorithm will do this for you.
Solution 3
The Floyd-Warshall algorithm would be a possible solution to your problem, but there are also other solutions to solve the all-pairs shortest path problem.
Solution 4
Shortest path is defined by the minimum number of vertexes treversed
it is same as minimum number of edges plus one.
you can use standard breadth first search and it will work fine. If you have more than one path connecting two vertices just save one of them it will not affect anything, because weight of every edge is 1.
Comments
-
Graviton almost 2 years
I have a list of interconnected edges (
E
), how can I find the shortest path connecting from one vertex to another?I am thinking about using lowest common ancestors, but the edges don't have a clearly defined root, so I don't think the solution works.
Shortest path is defined by the minimum number of vertexes traversed.
Note: There could be a multi-path connecting two vertices, so obviously breadth first search won't work -
John Kugelman over 14 yearsOnly needed if edges are weighted.
-
Graviton over 14 yearsbfs will tell me a path between two nodes; but it can't tell me which path is the shortest one.
-
monksy over 14 yearsI forgot about that... I assumed that his map of edges were weights.
-
seanmonstar over 14 yearsif not weighted, simply assume all edges weigh 1. still a good solution.
-
Artelius over 14 yearsOops, BFS gives you the shortest path for unweighted edges.