Thanks for all useful tips in your useful forum,
I am wondering if I can get help to make some changes on this C++ code for finding the least cost path for dijksta algorithm in specific case.
I would like to change the output to 2 lists, as follow
1-show the candidate list + the least code
2-a list to determine the source node and the next node
thanks
#include <vcl.h>
#pragma hdrstop
#include <vector>
#include <iostream>
using namespace std;
void printList(int i);
char toNode(int i);
#pragma argsused
int main(int argc, char* argv[])
{
int LC; // Lowest-Cost
int LCi; // Lowest-Cost index
int LCn; // Lowest-Cost node
int count = 0; // Iteration Number
int path = 0; // Path cost
int NextNodeA = 0; // Temporary
int NextNode[7] = {0,1,2,99,4,99,99}; // Next Node
// Least-Cost List and Candidate List
vector <int> LC_List;
vector <int> C_List;
// Path Links
// Also represents the Link-Costs Table
int RT[7][7] = {
{0, 5, 2, 4, 99, 99, 99},
{5, 0, 2, 99, 99, 2, 99},
{2, 2, 0, 99, 1, 99, 99},
{4, 99, 99, 0, 5, 99, 99},
{99, 99, 1, 5, 0, 1, 2},
{99, 2, 99, 99, 1, 0, 4},
{99, 99, 99, 99, 2, 4, 0}
};
// Nodes representations in Link-Costs Table
enum nodes
{
A = 0, B = 1, C = 2, D = 3,
E = 4, F = 5, G = 6
};
// Initial values
LC_List.push_back(C);
C_List.push_back(A);
C_List.push_back(B);
C_List.push_back(E);
// Print first iteration info
cout << "++Iteration No." << ++count << endl << "LC List: ";
for_each(LC_List.begin(), LC_List.end(), printList);
cout << endl << "C List: ";
for_each(C_List.begin(), C_List.end(), printList);
cout << endl << endl;
// Iterate til Candidate-List is empty
while ( !C_List.empty() ) {
LC = 99;
LCi = 0;
LCn = 0;
// Find Least-Cost path within Candidate List
for (int i=0; i<C_List.size(); i++)
if ( RT[C][C_List.at(i)]<LC )
{
LCi = i;
LC = RT[C][C_List.at(LCi)]; // found it!
LCn = C_List.at(LCi);
}
// Move it to Least-Cost List
LC_List.push_back(LCn);
// Erase it from Candidate List
C_List.erase(C_List.begin()+LCi);
// Push directly-connected nodes of the
// moved node to Candidate List
if ( LCn==E )
{
C_List.push_back(D);
C_List.push_back(F);
C_List.push_back(G);
}
// Print iterations info
cout << "Loop Number." << ++count << endl << "Lowest Cost List: ";
for_each(LC_List.begin(), LC_List.end(), printList);
cout << endl << "Cost List: ";
for_each(C_List.begin(), C_List.end(), printList);
cout << endl << endl;
// Calculate Least-Cost paths
for ( int i=0; i<C_List.size(); i++ ) {
for ( int j=0; j<LC_List.size(); j++ ) {
// In case of direct links
if ( LC_List.at(j)==C ) {
path = RT[LC_List.at(j)][C_List.at(i)];
NextNodeA = C_List.at(i);
} else {
path = RT[C][LC_List.at(j)] + RT[LC_List.at(j)][C_List.at(i)];
NextNodeA = LC_List.at(j);
}
// In case path cost is infinite
if ( path>99 ) path = 99;
// Print path info
cout << toNode(C) << " to " << toNode(C_List.at(i)) << " via " << toNode(LC_List.at(j));
cout << " = " << path << endl;
// Save Least-Cost path info
if ( RT[C][C_List.at(i)] > path )
{
RT[C][C_List.at(i)] = path;
NextNode[C_List.at(i)] = NextNodeA;
}
}
// Print Least-Cost path info
cout << "Lowest path = " << RT[C][C_List.at(i)] << endl << endl;
}
}
cout << "Dest. ++ Next Node ++ Cost" << endl;
for ( int i=0; i<7; i++ )
cout << " " << toNode(i)
<< " " << toNode(NextNode[i])
<< " " << RT[C][i] << endl;
getchar();
return 0;
}
// Print either Candidate List or Least-Cost List
void printList (int i)
{
cout << " " << toNode(i);
}
// Return node name
char toNode(int i)
{
switch (i)
{
case 0: return 'A'; break;
case 1: return 'B'; break;
case 2: return 'C'; break;
case 3: return 'D'; break;
case 4: return 'E'; break;
case 5: return 'F'; break;
case 6: return 'G'; break;
}
}
