c++algorithmgraphpathshortest

Point to point path in a Graph

I want an algorithm to be able to find an optimal path between two vertices on a graph (with positive int weights).The thing is my graph is relatively big (up to 100 vertices). I have considered the dijkstra algorithm but as I searched the net most implementions use the adjacency matrix which in my case will be 100x100.

If you could recommend me a certain source to read and learn from , or even better provide me with a c++ implementaion it will be great.

PS: The algorithm needs to output the required route and not just the shortest distance between two points.

Thank you for your time.

Solution

  • Have you looked into A*?

    Here's a good article to start reading: http://www.redblobgames.com/pathfinding/a-star/introduction.html