Final Proiect 1) Write a program that will implement a weighted graph and use Di

Question

Final Proiect 1) Write a program that will implement a weighted graph and use Dijkstra's Algorithm to calculate the shortest path from a start node to every other node in the graph. You may implement your graph using an edge list, adjacency list, or adjacency matrix structure. It must also implement a priority queue using a heap. Your program must provide the user with a prompt to allow the user to construct the graph. The prompt should provide 6 commands: add node, adde_edge, remove_edge, remove_node, Dijkstra, exit. a. add_node - Will add a node labeled with 'label' to the graph. A label will always be a character from a-z. If a node with that label already exists in the graph the program should not add a duplicate to the graph and should inform the user that a node with that label already exists b. add_edge - 'From' will be the label of the node that the edge starts from. 'TQ' will be the label of the node that the edge goes to 'Weight' will be the be the numerical weight to assign to the edge. You should only all one edge from a given node to another node. If the user tried to add an edge that already exists print out a message informing them that that operation is not allowed. c. remove edge

Explanation / Answer

Hello,

Below is the implemetation Dijkstra's shortest path algorithm. If you want to make any change in the code you can absolutely make it :)

//Code for shortest path

#include <stdio.h>
#include <limits.h>
#define V 9

int ShortPath(int Distance[], bool ShortPathSet[])
{
   int Minimum = INT_MAX, Minimum_Index;

   for (int v = 0; v < V; v++)
     if (ShortPathSet[v] == false && Distance[v] <= Minimum)
         Minimum = Distance[v], Minimum_Index = v;

   return Minimum_Index;
}
int solution(int Distance[], int n)
{
   printf("Vertex   Distance from Source ");
   for (int i = 0; i < V; i++)
      printf("%d tt %d ", i, Distance[i]);
}
void Dijk(int Ggraph[V][V], int source)
{
     int Distance[V];
     bool ShortPathSet[V];
     for (int i = 0; i < V; i++)
        Distance[i] = INT_MAX, ShortPathSet[i] = false;
     Distance[source] = 0;
     for (int cnt = 0; cnt < V-1; cnt++)
     {
       int u = ShortPath(Distance, ShortPathSet);
       ShortPathSet[u] = true;
       for (int v = 0; v < V; v++)
         if (!ShortPathSet[v] && Ggraph[u][v] && Distance[u] != INT_MAX
                                       && Distance[u]+Ggraph[u][v] < Distance[v])
            Distance[v] = Distance[u] + Ggraph[u][v];
     }
     solution(Distance, V);
}

int main()
{
   int Ggraph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                      {4, 0, 8, 0, 0, 0, 0, 11, 0},
                      {0, 8, 0, 7, 0, 4, 0, 0, 2},
                      {0, 0, 7, 0, 9, 14, 0, 0, 0},
                      {0, 0, 0, 9, 0, 10, 0, 0, 0},
                      {0, 0, 4, 14, 10, 0, 2, 0, 0},
                      {0, 0, 0, 0, 0, 2, 0, 1, 6},
                      {8, 11, 0, 0, 0, 0, 1, 0, 7},
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}
                     };

    Dijk(Ggraph, 0);
    return 0;
}

Hope, I have solved your problem. Thank you. :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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