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;
// 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;
}
}``````

Edited by Nick Evan: Removed color-tags.

3
Contributors
2
Replies
4
Views
7 Years
Discussion Span
Last Post by Nick Evan

Good Cop:
You've done good to get that far (and you used code tags). It shouldn't be that hard to take the code you've written (and the experience you gained writing it) to make it do something slightly different.