All pairs shortest path (stl binary heap implementation)

[Guest_imported]

Does ne one has the implementation of shortest path from one to many nodes using DIjkstra's Algorithm.

I am using binary heap implementation. I have successfully implmented the one to one shortest path Dijkstra's algorithm but facing some probelm in implementing the one to many versions.

Problem I am facing is I have found the shortest path between few pairs but if the path doesnot exists between the two pairs then instead of showing no path message it is showing me some junk values. Actually I am recursively doing the dijkstra'a without permanently labeling the visited nodes as I may need to visit the same node again and again. There is some probelm in the code if some one can give me a hint where I may be wrong or even can give me the implmentation of the same , my rpobelm will solved.

 

[Zyrenthian]

When you do find the shortest path (from what you said above it sounds like this part works), how are you printing it out? are you traversing the graph again? Also... what does your struct look like... are you using a linked list or a multi dimentional array? Knowing this i MAY be able to help but it has been a while since I took algorithm analysis.

matt

 

[rmcweb]

Here is rough pseudocode for a bottoms-up approach to this. The different distances are stored in a 2D matrix and everything in it is initialized; if there isn't a path it's set to a number like -1 or MAX_NUM to avoid getting "junk" when it comes time to run it.
(for int x=1; x= number of points; ++x)
(for int y=1; y= number of points; ++y)
(if (Matrix[x][y] != -1 or MAX_NUM))
{
(for int k=0; k<number of points; ++k)
{
if (Matrix[x][k]!= -1 || Matrix[k][y]!= -1)
Matrix[x][y]= Minimum(Matrix[x][y],
Matrix[x][k]+ Matrix[k][y]);
}
}
This is REALLY rough but I hope you get the general idea. Hope this helps
rmcweb

 

[rmcweb]

Hope this is a clearer version of what I'd posted before
for (int x=1; x<= number of points; ++x)
for (int y=1; y<= number of points; ++y)
{
if ((Matrix[x][k]!= -1) || (Matrix[k][y]!= -1))
{
for (int k=1; k<=number of points; ++k)
{
if ((Matrix[x][k]!= -1) || (Matrix[k][y]!= -1))
Matrix[x][y]= Minimum(Matrix[x][y],
Matrix[x][k]+ Matrix[k][y]);
}
}
}
rmcweb