/*
 *  Michael Gousie
 *  COMP 318  Spring 2026
 *  dijkstraWeb.cpp
 *
 *  Dijkstra's algorithm
 *  This is a partial implementation; minimumKnown() and main() are not
 *  shown, as well as no method for getting graph data.
 */

struct Graph {
   int numVertices;
   int adjMatrix [MAX][MAX];    // or do with pointer and dynamically allocate
};

struct pathTableEntry {
   bool pathKnown;     // done with this vertex?
   int distance;       // length of current shortest path
   int pathPred;       // index of predecessor on shortest path (huh?)
};

void initTable (int startVertex, const Graph& G, pathTableEntry T[]) {
        // assumes table T is pre-allocated
   int i;

   for (i = 0; i < G.numVertices; i++) {
      T[i].pathKnown = false; // path not found
      T[i].distance = Inf;    // assume this is defined
      T[i].pathPred = -1;     // no path at start
   }

   T[startVertex].distance = 0;
}

void printTable (const Graph& G, pathTableEntry T[]) {
   int i;

   cout << endl << "V  Dv  Pred" << endl;
   for (i = 0; i < G.numVertices; i++) {
      cout << i << "  " << T[i].distance << "  " << T[i].pathPred << endl;
   }
}

void Dijkstra (int startVertex, const Graph& G, pathTableEntry T[]) {
   int v;      // current vertex
   int nbr;    // neighboring vertex
   initTable (startVertex, G, T);

   for ( ; ; ) {
      v = minimumKnown (G, T);    // search through table T for smallest distance
                                  // for all vertices where the path is False; 
                                  // return vertex number (index) or -1
                                  // (this would use priority Q)
      if (v == -1)
         break;                   // loop's done!
    
      T[v].pathKnown = true;      // we're at the destination!
      for (nbr = 0; nbr < G.numVertices; nbr++)      // this is not a smart loop
         if (nbr != v) {          // don't bother looking at path to itself
            if (!T[nbr].pathKnown
                && T[v].distance + G.adjMatrix [v][nbr] < T[nbr].distance) {
               T[nbr].distance = T[v].distance + G.adjMatrix[v][nbr];  // relax
               T[nbr].pathPred = v;
            }
         }
   }
}