Program 4

 

Dijkstra’s Algorithm (Shortest Path)

/* Program to find shortest paths from a given vertex in a weighted connected graph to other vertices using Dijkstra’s algorithm*/
#include <stdio.h>
#include <stdlib.h>

#define MAXNODES 10
#define INF 9999

void fnDijkstra(int [MAXNODES][MAXNODES], int [MAXNODES], int [MAXNODES],
                int[MAXNODES], int, int, int);

int main(void) {
    int n, cost[MAXNODES][MAXNODES],dist[MAXNODES],visited[MAXNODES],
        path[MAXNODES],i,j,source,dest;
    printf("\nEnter the number of nodes\n");
    scanf("%d", &n);
    printf("Enter the Cost Matrix\n\n");
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            scanf("%d", &cost[i][j]);
    
    printf("Enter the Source vertex\n");
    scanf("%d", &source);
    printf("\n//For Source Vertex : %d shortest path to other vertices//\n", source);
    
    for (dest=0; dest < n; dest++) {
        fnDijkstra(cost,dist,path,visited,source,dest,n);
        if (dist[dest] == INF)
            printf("%d not reachable\n\n", dest);
        else {
            printf("\n");
            i = dest;
            do {
                printf("%d <--", i);
                i = path[i];
            } while (i!= source);
            printf("%d = %d\n", i, dist[dest]);
        }
    }
    return 0;
}

void fnDijkstra(int c[MAXNODES][MAXNODES], int d[MAXNODES], int p[MAXNODES], 
                int s[MAXNODES], int so, int de, int n) {
    int i,j,a,b,min;
    
    for (i=0;i<n;i++) {
        s[i] = 0;
        d[i] = c[so][i];
        p[i] = so;
    }
    s[so] = 1;
    
    for (i=1;i<n;i++) {
        min = INF;
        a = -1;
        for (j=0;j<n;j++) {
            if (s[j] == 0) {
                if (d[j] < min) {
                    min = d[j];
                    a = j;
                }
            }
        }
        if (a == -1) return;
        s[a] = 1;
        if (a == de) return;
        
        for (b=0;b<n;b++) {
            if (s[b] == 0) {
                if (d[a] + c[a][b] < d[b]) {
                    d[b] = d[a] + c[a][b];
                    p[b] = a;
                }
            }
        }
    }
}

Output:
Enter the number of nodes:6
Enter the Cost Matrix:
0 4 4 9999 9999 9999
4 0 2 9999 9999 9999
4 2 0 3 1 6
9999 9999 3 0 9999 2
9999 9999 1 9999 0 3 
9999 9999 6 2 3 0
Enter the Source vertex:
0
//For Source Vertex : 0 shortest path to other vertices//
0<--0 = 0
1<--0 = 4
2<--0 = 4
3<--2<--0 = 7
4<--2<--0 = 5
5<--4<--2<--0 = 8