Geek Answers Handbook

Dijkstra's algorithm with a 2d array

Over the past few days, I have been trying to implement this algorithm. So far, I have managed to create a dynamic 2d array and insert distances between nodes, a function to remove the path between nodes, and a function that tells me if there is a path between two nodes. Now I would like to implement a function that returns the shortest path from node A to node B. I know how the dijkstras algorithm works, and I read the wiki pseudocode without being able to write the code myself. I am really stuck here.

I was thinking about how the code should look and what should happen, so I created this function that tells me if there is a path between two nodes. Do I need additional help functions that make implementing dijkstras easier?

At the moment I have only 3 nodes, but the code that I would like to write should work for n nodes in general.

Any help is appreciated.

+5
source share
3 answers

You probably think a lot.

You need 2 things. The clean graphics structure that you understand. Good description of the algorithm you understand. If you have both. Just start writing code. The necessary helpers will become apparent along the way.

- change -
You will probably need some of the following data structures: std::vector std::list std::priority_queue

+5
source

: , :

  • . (- vector < vector < pair<int,int> > > g (n);)
  • , , . (, set priority_queue O(m log(n)))
  • , high_priority ( ), , .

Note. If you want to get the minimum path, save vector<int> previousand set it every time you update the distance to the top (for example v) previous[v] = index of vertex from where you came here. Your path is last, prev[last], prev[prev[last]],...,firstin reverse order.

+2
source

More articles:


All Articles