I need to make a weighted graph and use Dijkstra\'s algorithm to calculate the s
ID: 3911558 • Letter: I
Question
I need to make a weighted graph and use Dijkstra's algorithm to calculate the shortest path from a start node to other nodes in the graph. The following is code in my constructor file so far. I need to add an edge, remove an edge, add a node, remove a node, implement a priority queue, and implement Dijkstra's algorithm. How would I go about removing a node, adding a priority queue, and implementing Dijkstra's algorithm? Any help would be greatly appreciated!
//Function to add a node
void Graph::add_node(int node){
this->node = node;
visited = new bool [node];
adjacency = new int* [node];
for (int row = 0; row < node; row++){
adjacency[row] = new int [node];
for(int column = 0; column < node; column++) {
adjacency[row][column] = 0;
}
}
}
//Function to add an edge
void Graph::add_edge(int start, int end) {
if( start > node || end > node || start < 0 || end < 0){
cout<<"ERROR: Invalid edge! ";
}
else{
adjacency[start - 1][end - 1] = 1;
}
}
//Function to view the graph
void Graph::showGraph() {
for(int row = 0; row < node; row++) {
for(int column = 0; column < node; column++) {
cout<<adjacency[row][column]<<" ";
}
cout<<endl;
}
}
//function to remove an edge
void Graph::remove_edge(int start, int end){
if( start > node || end > node || start < 0 || end < 0){
cout<<"ERROR: Invalid edge! ";
}
else{
adjacency[start - 1][end - 1] = 0;
}
}
//function to remove a node
void Graph::remove_node(int node){
}
//function for priority queue
void Graph::PQueue(){
}
//function to implement Dijkstra's algorithm
void Graph::dijkstra(int graph, int source){
}
Explanation / Answer
**//function to delete a node//
void delete_node(int u)
{
int i,j;
if(n==0)//n is total no node
{
printf("Graph is empty ");
return;
}
if( u>n )
{
printf("This node is not present in the graph ");
return;
}
for(i=u;i<=n-1;i++)
for(j=1;j<=n;j++)
{
adj[j][i]=adj[j][i+1]; /* Shift columns left */
adj[i][j]=adj[i+1][j]; /* Shift rows up */
}
n--; /*Decrease the number of nodes in the graph */
}
//function to implement dijkstra
int find_minDistance(int dist[], bool visited[])
{
int min = INT_MAX,index;
for (int v = 0; v < V; v++)
if (visited[v] == false && dist[v] <= min)
min = dist[v], index = v;
return index;
}
int printresult(int dist[], int n)
{ int i;
printf("Vertex Distance from Source ");
for (i = 0; i < V; i++)
printf("%d tt %d ", i, dist[i]);
}
void dijkstra_solution(int adj[V][V], int source)
{
int dist[V];
bool visited[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, visited[i] = false;
dist[source] = 0;
for (int count = 0; count < V-1; count++)
{
int u = find_minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < V; v++)
if (!visited[v] && adj[u][v] && dist[u] != INT_MAX
&& dist[u]+adj[u][v] < dist[v])
dist[v] = dist[u] + adj[u][v];
}
print_result(dist, V);
}