Question on Shortest path algorithm - Dijkstra

Hello. I have implemented the Dijkstra shortest path algorithm, it
works fine but I have one question on how I can improve something.
I want to find all the possible shortest paths from a node since there
is a possibility to exist more than one shortest paths with the same
distance.

Does anyone has any idea how this could be done?

Code

double Dijkstra_Least_Cost(vector< vector<int> > graph, int
start_vertex, ofstream &outputfile)
{
unsigned int graph_size = graph.size();
unsigned int D_size = graph_size + 1;
unsigned int ii, jj, W;
unsigned int kk = 1;
double average_distance = 0;
double temp_d = 0;

vector <int> distance;
vector <int> predecessor;
vector <bool> not_checked;
map <int,int> intermediate_nodes;
map<int, int>::const_iterator iter;
vector< vector<int> > betweennes_l(D_size,
vector<int>(D_size,0));

outputfile <<"Starting from node: " << start_vertex << endl;

//initialize the vectors
distance.push_back(0); //in order to start from 1.
not_checked.push_back(true); //in order to start from 1.
predecessor.push_back(0); //in order to start from 1.

for (ii = 1; ii < graph_size; ii ++)
{
distance.push_back(graph[start_vertex][ii]);
not_checked.push_back(true);
predecessor.push_back(start_vertex);

}

distance[start_vertex] = 0; //set start distance to
zero
predecessor[0] = -1;
predecessor[start_vertex] = -1; //default start
predecessor

not_checked[start_vertex] = false; //mark as checked vertex

bool done = false;

int testing = 0;
while (!done)
{
int V, shortest_d = BIG;

for (jj = 1; jj < graph_size; jj ++)
{
//if it is <= we get a different route.
if (distance[jj] <= shortest_d &&
not_checked[jj])
{
V = jj;
shortest_d = distance[V];
}
}

not_checked[V] = false; //for every neighbor W of V

//edge relaxation
for (W = 1; W < graph_size; W++)
{
if (graph[V][W] < BIG && not_checked[W])
{ //unchecked neighbor
if (distance[W] > distance[V] +
graph[V][W])
{
distance[W] = distance[V] +
graph[V][W];
predecessor[W] = V;
}
}

while (kk < graph_size && !not_checked[kk])
kk++;
done = (kk == graph_size);//done=true if there are no
unchecked
neighbors
}
//*******************************************PRINT LEAST COST
TO NODES
for (ii = 1; ii < graph_size; ii++)
{
temp_d+=distance[ii];
outputfile << "To arrive at node " << ii << " will
cost" <<
distance[ii] << endl;
}
average_distance = temp_d / (graph_size-2);
//-2 because we dont count itself and also
// the graph vector is 1 more than the number of nodes

//E4
cout << endl;

//*******************************************PRINT LEAST COST
TO NODES

cout << "Shortest Paths" << endl; //Print out all shortest
paths
stack<int> temp; //No recursion- use stacks
for (ii = 1; ii < graph_size; ii++)
{
int m = ii;
int m1;

while (predecessor[m] != -1)
{
m1 = m;
temp.push(m);
//intermediate_nodes[m]++; //how many times a
node was used along
the
// paths. we
will count the paths of length > 1
m = predecessor[m];
betweennes_l[m][m1]++;
intermediate_nodes[m]++; //how many times a
node was used along the

//paths. we will count the paths of length > 2
}

int flag = 0;

while ( !temp.empty() )
{
if (flag ==0 )
{
cout << start_vertex;
}
cout << "-"<< temp.top();
flag++;
temp.pop();
}
cout << endl;
}

for (iter=intermediate_nodes.begin(); iter !=
intermediate_nodes.end(); ++iter)
{
if (iter->first != start_vertex)
{
cout << iter->first << ": " << iter->second <<
endl;
}
}
cout << endl;

cout << "Number of times each link is counted for the Shortest
Path"
<< endl;

for ( ii = 1; ii < graph_size; ii++)
{
for (jj = 1; jj < graph_size; jj++)
{
if (betweennes_l[ii][jj] != 0 )
{
cout << ii << "-"<< jj << "=" <<
betweennes_l[ii][jj]<< endl;
}
}
}

return average_distance;

}

Cheers
costas

.

Relevant Pages

  • Re: Could use some help...:)
    ... cout << endl ... int B::operator (unsigned row, unsigned column) ...
    (comp.lang.cpp)
  • valarray iterators?
    ... I've did some some numerical programs in C/C++ before, ... const int MAX=10; ... cout << endl; ...
    (comp.lang.cpp)
  • STL set class
    ... set <int> s0; ... // Create an empty set s1 with the key comparison ... cout << endl; ...
    (microsoft.public.vc.stl)
  • Cant see DLL symbols in debugger.
    ... APPIMPEXP extern int applic_datum; ... << endl; ... cout << endl; ... Dynlib2 is similar to dynlib1. ...
    (microsoft.public.vstudio.development)
  • Help preventing weak software
    ... template <typename T> ... int main ... cout << endl; ...
    (comp.lang.cpp)