Djikstra's Algorithm in C++

Question

I am writing Djikstra's algorithm in C++, and am having trouble getting the code to print anything other than the path from A->A. I need to get it to find the path from A->X where X is any one of the nodes A-I.

Expected Output
Actual Output

#include <climits>
#include <fstream>
#include <iostream>
using namespace std;

const int V = 9;
// Function to print shortest path from source to j
// using parent array
void printPath(int parent[], int j) {
  char str = j;
  // Base Case : If j is source
  if (parent[j] == -1) {
    cout << str << " ";
    return;
  }

  printPath(parent, parent[j]);

  // printf("%d ", j);
  cout << str << " ";
}

int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
  int minimum = INT_MAX, ind;

  for (int k = 0; k < V; k++) {
    if (Tset[k] == false && distance[k] <= minimum) {
      minimum = distance[k];
      ind = k;
    }
  }
  return ind;
}

void DijkstraAlgo(int graph[V][V], char sourceNode,
                  char endNode) // adjacency matrix
{
  int distance[V]; // array to calculate the minimum distance for each node
  bool Tset[V];    // boolean array to mark visited and unvisited for each node
  int parent[V];   // Parent array to store shortest path tree
                 // Value of parent[v] for a vertex v stores parent vertex of v
                 // in shortest path tree.

  for (int k = 0; k < V; k++) {
    distance[k] = INT_MAX;
    Tset[k] = false;
  }
  parent[sourceNode] = -1;  // Parent of root (or source vertex) is -1.
  distance[sourceNode] = 0; // Source vertex distance is set 0

  for (int k = 0; k < V; k++) {
    int end = miniDist(distance, Tset);
    Tset[end] = true;
    for (int k = 0; k < V; k++) {
      // updating the distance of neighbouring vertex
      if (!Tset[k] && graph[end][k] && distance[end] != INT_MAX &&
          distance[end] + graph[end][k] < distance[k]) {
        distance[k] = distance[end] + graph[end][k];
        parent[k] = end;
      }
    }
  }
  cout << "Vertex\t\tDistance from source vertex\t\t Path" << endl;
  int k = sourceNode;
  char str = k;
  // cout<<str<<"\t\t\t"<<distance[k]<<endl;
  cout << str << "\t\t\t" << distance[k] << "\t\t\t\t\t\t\t\t";
  printPath(parent, k);
  cout << endl;
}

int main() {
  char choice1, choice2;
  ifstream inFile;
  inFile.open("graph.txt");
  int graph[V][V];
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++)
      inFile >> graph[i][j];
  }
  cout << "Nodes: "
       << "A, B, C, D, E, F, G, H, I" << endl;
  cout << "Enter starting node: ";
  cin >> choice1;
  cout << "Enter ending node: ";
  cin >> choice2;
  cout << endl;
  DijkstraAlgo(graph, choice1, choice2);

  inFile.close();
  return 0;
}

So, I have to be able to pass the endNode parameter to something somehow, correct?

Answer 1

The main issue lies here:

int miniDist(int distance[], bool Tset[]) 

In your minimum distance calculation, you don't exclude the source vertex. All other vertices have INT_MAX distance and the source has 0 distance, so it gets picked. Try going through the algorithm once again to fix your implementation.