distance b/w 2 nodes in undirected graph
Hi,
Is there any algorithm that finds the distance b/w 2 arbitrarily chosen nodes in an undirected graph. Please point me to such a resource.
Thanks
Bye
You could start with BFS.
But for common game-related needs, where you want to look for a distance of two points on a map, A-star is usually a better choice.
But for common game-related needs, where you want to look for a distance of two points on a map, A-star is usually a better choice.
Breadth-first search if unweighted.
Dijkstra if weighted with no negative weights.
Bellman-Ford if weighted with negative weights.
All these search the minimum distance between a node and all other nodes, but you can stop them as soon as the distance to the second node is known.
Dijkstra if weighted with no negative weights.
Bellman-Ford if weighted with negative weights.
All these search the minimum distance between a node and all other nodes, but you can stop them as soon as the distance to the second node is known.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement