CODEWITHSUNDEEP
c++multidimensional-arraydijkstra
ogward
ogward

Reputation: 1193

Dijkstra's algorithm with an 2d-array

For the past few days I've tried to implement this algorithm. This far I've managed to make a dynamic 2d array and insert the distances between nodes, a function to remove a 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 dijkstras algorithm works and I've read the pseudo code on wiki without being able to write any code my self. I'm really stuck here.

I've been thinking about how the code should look like and what should happen thats why I've made that function that tells me if theres a path between two nodes. Do I need any more help functions which would make implementing of dijkstras easier?

For now I have only 3 nodes but the code I would like to write needs to work in general for n nodes.

Any kind of help is appreciated.

Upvotes: 5

Views: 8656

Answers (3)

log0
log0

Reputation: 10917

You are probably thinking to much.

You need 2 things. A clean graph structure you understand. A good description of the algorithm you understand. If you have both. Just start writing some code. Helpers needed will become obvious on the way.

-- edit --
You will probably need some of the following datastructures
std::vector std::list std::priority_queue

Upvotes: 5

Mihran Hovsepyan
Mihran Hovsepyan

Reputation: 11088

Edit: Code deleted, and I'm going to give hints:

  1. Store graph as list of adjacency lists of each vertex. (something like this vector < vector < pair<int,int> > > g (n);)
  2. Use some data-structure to keep track what is the vertex with minimal distance in current state. (maybe set, or priority_queue to have O(m log(n)) complexity)
  3. Each time take high_priority vertex (vertex with minimal current distance), delete it from your data_structure and update distances of adjacent to deleted one vertexes.

Note: If you want to get minimal path as well, then keep some vector<int> previous and each time when updating distance of vertex (say v) set previous[v] = index of vertex from where you came here. Your path is last, prev[last], prev[prev[last]],...,first in reversed order.

Upvotes: 2

Jav_Rock
Jav_Rock

Reputation: 22245

I found several codes for this algorithm, but maybe it is better the simplest one in order to undertand it better, so you can check the differences between yours and this one, and complete yours. It is always better to program your way.

Have a look at this one and see if it helps.

http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

Good luck.

Upvotes: 2

Related Questions