Task-5
Implement Dijkstra's algorithm to compute the shortest path through a graph.
Algorithm:
Algorithm ShortestPaths(v, cost, dist, n)
// dist[j], 1 ≤ j ≤ n, is set to the length of the shortest
// path from vertex v to vertex j in a digraph G with n
// vertices. dist[v] is set to zero. G is represented by its
// cost adjacency matrix cost[1 : n, 1 : n].
{
  for i := 1 to n do
  { // Initialize S.
    S[i] := false; dist[i] := cost[v, i];
  }
  S[v] := true; dist[v] := 0.0; // Put v in S.
  for num := 2 to n − 1 do
  {
    // Determine n − 1 paths from v.
    Choose u from among those vertices not
    in S such that dist[u] is minimum;
    S[u] := true; // Put u in S.
    for (each w adjacent to u with S[w] = false) do
    // Update distances.
    if (dist[w] > dist[u] + cost[u, w]) then
      dist[w] := dist[u] + cost[u, w];
  }
}
Program:
#include <stdio.h> 
#include <limits.h>
#define M 8

int n;

void spath(int graph[n][n], int u) {
    int dist[M];
    int s[M] = {0};
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
    dist[u] = 0;
    for (int i = 0; i < n - 1; i++) {
        int v;
        int min = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (dist[j] < min && s[j] == 0) {
                min = dist[j];
                v = j;
            }
        }
        s[v] = 1;
        for (int j = 0; j < n; j++) {
            if (graph[v][j] != 0 && s[j] == 0) {
                if (dist[j] > dist[v] + graph[v][j]) {
                    dist[j] = dist[v] + graph[v][j];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
}

int main() {
    printf("Enter the number of vertices (up to %d): ", M);
    scanf("%d", &n);

    int graph[M][M];
    printf("Enter the adjacency matrix (use 0 for no direct path):\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int startNode;
    printf("Enter the starting node (0 to %d): ", n - 1);
    scanf("%d", &startNode);

    spath(graph, startNode);
    return 0;
}
Output:
/tmp/q6mNdkXwgB.o
Enter the number of vertices (up to 8): 8
Enter the adjacency matrix (use 0 for no direct path):
0 0 0 0 0 0 0 0
300 0 0 0 0 0 0 0
1000 800 0 0 0 0 0 0
0 0 1200 0 0 0 0 0
0 0 0 1500 0 250 0 0
0 0 0 1000 0 0 900 1400
0 0 0 0 0 0 0 1000
1700 0 0 0 0 0 0 0
Enter the starting node (0 to 7): 4
3350 3250 2450 1250 0 250 1150 1650 


=== Code Execution Successful ===