BTW, determining the path at that point is fairly straight forward (at least I think so).
--- "Joseph A. Marrero" <[EMAIL PROTECTED]> wrote: > 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/ > _________________ Joseph A. Marrero http://www.l33tprogrammer.com/ ____________________________________________________________________________________ Tonight's top picks. What will you watch tonight? Preview the hottest shows on Yahoo! TV. http://tv.yahoo.com/
