dijkstra_Shortest_path.txt

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int graph[6][3] = {{0,2,4},{0,1,3},{1,3,2},{1,5,1},{3,4,6},{2,4,5}};

void dijkstra(vector<vector<pair<int, int>>> &adj_list, vector<bool> &visited,
              vector<int> &parents, vector<int> &dist)
{
    int src = 0;

    dist[0] = 0;

    for (int i = 0; i < 6; i++) {
        int v = -1;

        for (int j = 0; j < 6; j++) {
            if (!visited[j] && (v == -1 || dist[j] < dist[v])) {
                v = j;
            }
        }
        if (dist[v] == INT_MAX)
            break;

        visited[v] = true;

        for (auto edges : adj_list[v]) {
            int to = edges.first;
            int weight = edges.second;

            if (dist[v] + weight < dist[to]) {
                dist[to] = dist[v] + weight;
                parents[to] = v;
            }
        }
    }
}

int main()
{
    vector<vector<pair<int,int>>> adj_list;
    adj_list.resize(6);
    for (int i = 0; i < 6; i++) {
        adj_list[graph[i][0]].push_back(make_pair(graph[i][1], graph[i][2]));
    }
    vector<bool> visited;
    vector<int> dist;
    vector<int> parents;
    vector<int> edges;

    dist.assign(6, INT_MAX);
    parents.assign(6,0);
    visited.assign(6, false);

    dijkstra(adj_list, visited, parents, dist);
    for (int i = 5; i != 0; i = parents[i]) {
        edges.push_back(i);
    }
    edges.push_back(0);
    //reverse(edges.begin(), edges.end());
    cout << "Shortest path from 0 to 5 - " << endl;
    while(!edges.empty()) {
        cout << edges.back() << " ";
        edges.pop_back();
    }
    cout << endl;
    return 0;
}