I am trying to create an interactive map sort of game, where an army actor can be ordered to move to a province. What I am struggling with is how the actor should choose the best path as there might be several paths to the same destination of varying length. Quick research brought me to an idea to use a path graph, a graph showing the several provinces (represented as letters) with their connections to other provinces (as lines) and with the length of the path written over the line (a number). Now ideas are easy, the problem is that I’m not quite sure how best to implement it. I thought of having an array for each province linking all the other provinces with the length however for the actor to loop through each of these would be very demanding. Anyone here with a way to implement this or perhaps a better idea overall.
Finding the shortest path in a graph is a well known problem and there are plenty algorithms for it. One of the most common is “Dijkstra’s algorithm”, not sure if this is the same one which you found during your research.
You can search for some Dijkstra’s algorithm implementation to see how people approached storing the information about vertices. It will be difficult for me to explain it in the comment section but I also used array approach during my studies. Wikipedia has a pseudocode in it’s page which can be useful: Dijkstra's algorithm - Wikipedia
I have used this algorithm for Rod networks when I was in college.
In the previous comment, I can see a link where the algorithm is explained with diagrams.
If you make the concept clear then you can use the C++ code which I am going to provide. But it is not possible for me to share in the comment.
It is nothing but the generalization of the BFS algorithm.
Have a look at this: Dijkstra’s shortest path algorithm in C++
