There is an undirected graph. You need to store all edge weights in a two-dimensional array cost[][], and calculate the shortest distance from the source node 0 to all other nodes. Suppose there are at most 100 nodes. If there is no edge between two nodes, we set their weight to a very large number, MAX_DIS=999999, to denote these two nodes are not connected directly.
In this exercise, you are required to fulfill the following two tasks.
Initialize Cost Array Initially, we have the array cost[100][100] to store the edge cost. We input the total nodes number n and edges number m, and the input all edges with <x,y,w> format, where w is the weight of edge (x,y). If there is no edge between two nodes, we set the cost MAX_DIS.
Calculate Shortest Distance. With the cost array, we need to compute the shortest distance between node 0 and all other nodes. Also, we need to initialize the distance array distance[100] at first. Then in each loop, we first find the min distance distance[w] and update other distance distance[v] if node v is adjacent to w.
//Below is my code for this challenge, but it is not working properly for all the test cases. It works fine for some but I can't figure out where is the problem. I hope this is a good challenge to be solved and that is why I am posting it here. Can you guys help me debug this code...
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_NODES 100
#define MAX_DIS 999999
int cost[MAX_NODES][MAX_NODES];
int distance[MAX_NODES];
void initial(int m, int n);
void Dijkstra(int n);
void initial(int m, int n)
{
/*
let user input all edges and their weights and initialize cost[][].
note that if no edge between (x,y), set cost[x][y]=MAX_DIS
and cost[a][b]=cost[b][a] for the undirected graph.
Fill in your code here...
*/
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cost[i][j] = MAX_DIS;
}
}
cost[0][0] = 0;
int weight,x,y;
for(i=0; i < m; i++){
scanf("%d %d %d", &x,&y,&weight);
cost[x][y] = weight;
cost[y][x] = weight;
}
}
void Dijsktra(int n)
{
/*
Fill in your code here...
calculate the distance from node 0 to all other nodes.
*/
int i;
int S[n];
S[0] = 1;
int all_visited = 0;
for(i=1;i<n;i++){
S[i] = -1;
}
for(i=0;i<n;i++){
distance[i] = cost[0][i];
}
while(all_visited != 1){
int temp = MAX_DIS;
int pos = -1;
for(i=1;i<n;i++){
if(S[i] == -1 && cost[0][i] <= temp){
temp = cost[0][i];
pos = i;
}
}
S[pos] = 1;
for(i=0;i<n;i++){
if(S[i] == -1)
break;
}
if(i==n)
all_visited = 1;
for(i=1; i<n; i++){
distance[i] = (int)fmin(distance[i], distance[pos] + cost[pos][i]);
}
}
}
int main()
{
int m,n;
printf("Input the number of nodes:\n");
scanf("%d",&n);
printf("Input the number of edges:\n");
scanf("%d",&m);
printf("Input these edges:\n");
initial(m,n);
Dijsktra(n);
for(int i=0;i<n;i++)
printf("%d ",distance[i]);
return 0;
}
This is test case for which my code is failing -
Input the number of nodes: 8 Input the number of edges: 10 Input these edges: 0 1 2, 1 2 9, 2 3 4, 3 5 7, 2 4 8, 5 6 10, 6 7 8, 7 5 1, 7 3 4, 0 4 10
Expected output - 0 2 11 15 10 20 27 19
My output - 0 2 11 15 10 999999 999999 999999