Shortest path between two given nodes in unweighted graph/tree

3
votes

I am looking for an algorithm to determine the shortest path between two nodes in an unweighted graph by using the adjacency matrix . I know Dijkstra and Bellman - Ford, but none that found are specific to determine the shortest path between two given nodes.

Any help is greatly apreciated

1
algorithmshortest-path
This question may be so general/theoretical as to be better answered on cs.stackexchange.com. See the graphs tag: cs.stackexchange.com/questions/tagged/graphs - Jacob Foshee
possible duplicate of using Dijkstra algorithm to find shortest path in an adjacency matrix. Also, this paper describes how to compute the shortest path using matrix multiplication. - Ted Hopp
Out of curiosity, why do you think that Dijkstra's algorithm and Bellman-Ford can't be used to find the shortest path between two nodes? - templatetypedef
i'm not saying they cannot be used, just that the variations i found did not match my requirements. - Dorin Rusu

1 Answers

7
votes

One simple option is to run a breadth-first search starting at the first node until the second node is found. If you store parent pointers for each node, you can then read off the path from the first node to the second. Moreover, this runs in linear time in the size of the graph.

Hope this helps!