I solved such a problem a while back on my own free time when I was taking Graph Theory. I did not use an adjacency matrix as it is not necessary. The only data structures you need to use are a list (or vector), a min-heap (use std::priority_queue), and a map. I then made classes to represent a vertex, an edge, and a graph data structure. Once you have some infrastructure in place it is an exercise in coding up Dijkstra's algorithm. Wikipedia has some pseudo code for it at http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
Some ideas/tips: - Each vertex needs to have a list of adjacent edges it could take. - Each edge only really needs to know the destination vertex and its weight. - Each vertex needs to know its distance, the data stored at a vertex, and a bool to determine if you have visited this vertex already. Make sure to see the pseudo code on this URL: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm These ideas are from my own implementation. I hope they were helpful. http://www.l33tprogrammer.com/index.php?page=blog&bid=26 --- sejal patel <[EMAIL PROTECTED]> wrote: > > > I need help in this prog. > input / output > Please enter starting and ending nodes and a graph: > 4 1 5 1 0 1 2 2 2 2 1 3 1 > 3 2 > > this is prog to find shortest path using adjacency list. > 4 is source > node 1 is destination node and 5 is size of matrx that is > 5*5( > adjacency matrix) 1 0 2 2 2 2 1 3 1 is matrix list. > we can represent it this (1 0 2 2 2 2 1 3 1) as > 01101 > 00100 > 10010 > 01010 > 00101 > > first is one so put zero then put 1 ,next is 1 so no zero > put 1,next > 2 put 0 0 then put 1 and so on... > basicaly count no of zero's. > > now using this i have to find shortest path > and answer is 3 2 .where 3 lenght of path and 2 no of > short paths. > > this represent would work for any input. > > i am trying using vector in c++. > i dont know how to do this? > please help me. > > _________________ Joseph A. Marrero http://www.l33tprogrammer.com/ ____________________________________________________________________________________ Pinpoint customers who are looking for what you sell. http://searchmarketing.yahoo.com/
