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

Recommended Answers

All 2 Replies

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.

Bad Cop:
You found the code on the net (or it was given to you by your tutor) and now you want us to modify it to match your new spec.

Bad Cop:
You found the code on the net

Yup. Here it is

commented: Nice detective work - DCI Nick :) +19
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.