//     (0)
//    /   \
//   10     3
//  /        \
// (1)---1---(2)
//   \       /
//    2     8
//     \   /
//      (3)
//       |
//       7
//       |
//      (4)
//

#include <limits.h>
#define V 5 // number of vertices

int graph[V][V] = {
    /* Our graph */
    {0, 10, 3, 0, 0},
    {10, 0, 1, 2, 0},
    {3, 1, 0, 8, 0},
    {0, 2, 8, 0, 7},
    {0, 0, 0, 7, 0}};

// void dijkstra(int graph[V][V], int src, int dist[V]);
//
// void dijkstra(int graph[V][V], int src, int dist[V]) {
// }

void dijkstra(int graph[V][V], int src, int dist[V]) {
    int visited[V]; // track processed vertices

    // initialize distances
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0;

    // main loop: V-1 iterations
    for (int count = 0; count < V - 1; count++) {
        // pick the unvisited vertex with the smallest dist
        int u = -1;
        int min = INT_MAX;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] < min) {
                /* Note that in the first iteration src will get selected */
                min = dist[v];
                u = v;
            }
        }

        if (u == -1)
            break; // no more reachable vertices
        visited[u] = 1;

        // update neighbors
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v]          // if path exists, and v is not visited
                && dist[u] != INT_MAX               // Check that the distance to currenct is not INT_MAX
                && dist[u] + graph[u][v] < dist[v]) // If the new distance is less than the existing
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}