dijkstra

/*
in.txt
8
1 2 4
1 4 5
4 5 7
2 6 2
6 7 3
6 8 1
*/

#include <iostream>
#include <fstream>

#define INTS_MAX -1
#define MAX_INT 99

using namespace std;
ifstream f("in.txt");


void initialiseGraph(int graph[][MAX_INT], int nodes) {
    for (int i = 1; i <= nodes; i++) {
        for (int j = 1; j <= nodes; j++) {
            graph[i][j] = INTS_MAX;
        }
    }
}

void readGraph(int graph[][MAX_INT], int edges) {
    for (int i = 1; i <= edges; i++) {
        int x, y, w;
        f >> x >> y >> w;
        graph[x][y] = w;
    }
}

void showGraph(int graph[][MAX_INT], int nodes) {
    for (int i = 1; i <= nodes; i++) {
        for (int j = 1; j <= nodes; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

void initiate(int nodes, int shortest_paths[], int start) {
    for (int node = 1; node <= nodes; node++) {
        shortest_paths[node] = INTS_MAX;
    }
    shortest_paths[start] = 0;
}

void relax(int graph[][MAX_INT], bool unvisited[], int shortest_path[], int nodes, int current_node) {
    for (int node = 1; node <= nodes; node++) {
        int w = graph[current_node][node];
        if ((w != INTS_MAX && unvisited[node]) &&
            (shortest_path[node] == INTS_MAX || shortest_path[node] > w + shortest_path[current_node])) {
            shortest_path[node] = w + shortest_path[current_node];
        }
    }
}

int extractMin(int shortest_path[], bool unvisited[], int nodes) {
    int mins = INTS_MAX;
    int minNode = INTS_MAX;
    for (int node = 1; node <= nodes; node++) {
        if ((shortest_path[node] != INTS_MAX && unvisited[node]) && (mins == INTS_MAX || mins > shortest_path[node])) {
            mins = shortest_path[node];
            minNode = node;
        }
    }
    return minNode;
}

void Dijkstra(int graph[][MAX_INT], int source_node, int nodes) {
    int shortest_path[MAX_INT];
    initiate(nodes, shortest_path, source_node);

    int hasToVisit = nodes;
    bool unvisited[MAX_INT];
    for (int node = 1; node <= nodes; node++) {
        unvisited[node] = true;
    }
    while (hasToVisit != 1) {
        int currentNode = extractMin(shortest_path, unvisited, nodes);
        unvisited[currentNode] = false;
        hasToVisit--;
        relax(graph, unvisited, shortest_path, nodes, currentNode);
    }

    for (int node = 1; node <= nodes; node++) {
        if (shortest_path[node] == INTS_MAX) {
            cout << "INF" << '\t';
        } else {
            cout << shortest_path[node] <<'\t';
        }
    }
}

int main() {
    int nodes, edges, weight;
    f >> nodes >> edges >> weight;
    int graph[MAX_INT][MAX_INT];
    initialiseGraph(graph, nodes);
    readGraph(graph, edges);
    showGraph(graph, nodes);
    int source_node = 1;
    Dijkstra(graph, source_node, nodes);
    return 0;
}