I need help implementing my setGraph(). It is not implementing it properly when

Question

I need help implementing my setGraph(). It is not implementing it properly when it goes to print everything out. I have an array of vertexNames because I later plan on assigning each column in the matrix a name.

#include <iostream>
#include <string>
#define NODE 6

using namespace std;

class Dijkstra
{
private:
   int graph[NODE][NODE];
   int distance[NODE];
   int vertex[NODE];
   string vertexNames[NODE];
   bool Found[NODE];
   int startingVertex;

public:
   void setGraph();
   void initialize();
   int findNextNode();
   void algorithm();
   void PrintPath(int);
   void Print();
};

int main()
{  
   Dijkstra Graph;
   Graph.setGraph();
   Graph.algorithm();
   Graph.Print();

   system("Pause");
}

void Dijkstra::setGraph()
{
   int graph[NODE][NODE] = {
       { 999, 2, 5, 9, 999, 999 }, //Macomb
       { 2, 999, 2, 4, 999, 999 }, //Hope
       { 5, 2, 999, 1, 4, 999 }, //Love
       { 9, 4, 1, 999, 1, 5 }, //Peace
       { 999, 999, 4, 1, 999, 2 }, //Belief
       { 999, 999, 999, 5, 2, 999 }, }; //Chicago

   startingVertex = 0;
}

void Dijkstra::initialize()
{
   for (int i = 0; i < NODE; i++)
   {
       Found[i] = false;
       vertex[i] = -1;
       distance[i] = 999;
   }
   distance[startingVertex] = 0;
}

int Dijkstra::findNextNode()
{
   int distMin = 999;
   int nextNode;

   for (int i = 0; i < NODE; i++)
   {
       if ((!Found[i]) && (distMin >= distance[i]))
       {
           distMin = distance[i];
           nextNode = i;
       }
   }
   return nextNode;
}

void Dijkstra::algorithm()
{
   initialize();

   int minDist = 999;
   int nextNode;
   int count = 0;

   while (count < NODE)
   {
       nextNode = findNextNode();
       Found[nextNode] = true;

       for (int i = 0; i < NODE; i++)
       {
           if ((!Found[i]) && (graph[nextNode][i] > 0))
           {
               if (distance[i] > distance[nextNode] + graph[nextNode][i])
               {
                   distance[i] = distance[nextNode] + graph[nextNode][i];
                   vertex[i] = nextNode;
               }
           }
       }
       count++;
   }

}

void Dijkstra::PrintPath(int node)
{
   if (node == startingVertex)
       cout << (char)(node + 97) << "..";
   else if (vertex[node] == -1)
       cout << "No path from “<<source<<”to " << (char)(node + 97) << endl;
   else
   {
       PrintPath(vertex[node]);
       cout << (char)(node + 97) << "..";
   }
}

void Dijkstra::Print()
{
   for (int i = 0; i < NODE; i++)
   {
       if (i == startingVertex)
           cout << (char)(startingVertex + 97) << ".." << startingVertex;
       else
           PrintPath(i);
       cout << "->" << distance[i] << endl;
   }
}

Thanks for your help!

Explanation / Answer

    #include <stdio.h>

    #include <limits.h>

    #define V 9

    int Dijkstra(int dist[], bool sptSet[])

    {

        // Initialize min value

        int min = INT_MAX, min_index;

        for (int v = 0; v < V; v++)

            if (sptSet[v] == false && dist[v] <= min)

                min = dist[v], min_index = v;

        return min_index;

    }

    int printSolution(int dist[], int n)

    {

        printf("Vertex   Distance from Source ");

        for (int i = 0; i < V; i++)

            printf("%d %d ", i, dist[i]);

    }

    void dijkstra(int graph[V][V], int src)

    {

        int dist[V];
        bool sptSet[V];

        for (int i = 0; i < V; i++)

            dist[i] = INT_MAX, sptSet[i] = false;

        // Distance of source vertex from itself is always 0

        dist[src] = 0;

        // Find shortest path for all vertices

        for (int count = 0; count < V - 1; count++)

        {

            int u = Dijkstra(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]

                        + graph[u][v] < dist[v])

                    dist[v] = dist[u] + graph[u][v];

        }

   
        printSolution(dist, V);

    }

    // driver program to test above function

    int main()

    {

        int graph[V][V] =

                        { 999, 2, 5, 9, 999, 999 }, //Macomb
                { 2, 999, 2, 4, 999, 999 }, //Hope
                { 5, 2, 999, 1, 4, 999 }, //Love
                { 9, 4, 1, 999, 1, 5 }, //Peace
                { 999, 999, 4, 1, 999, 2 }, //Belief
                        { 999, 999, 999, 5, 2, 999 }, };
   

        dijkstra(graph, 0);

        return 0;

    }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.