Graph/dijkstraAlgorithm.cpp at master · Brajmohank1/Graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;


typedef pair<int,int> iPair;
// implementation of weighted graph in c++ using vector with pair;

void pritGraph(vector<iPair> adj[] , int n){


    // printing graph with their source to destinatiojn and corresponding their weight;

    for(int i =0 ; i < n ; i++){

        cout<<"Sorce vertex is " << i << " - > destiantion and weight \n\n\n";
        for(auto x: adj[i]){

            int dest = x.first;
            int weight = x.second;

            cout<<dest << "  " << weight << "\n";
        }


        cout<<"\n\n\n\n";
    }
}


vector<ll> dijkstraAlgorithm(vector<vector<iPair>> &adj , int n  , int src){

    // Dijkstra algorithm is used for find shortest distance of all vertices from a source vertices

    priority_queue<iPair , vector<iPair> , greater<iPair>> pq;
    vector<ll> dist(n , INF);

    dist[src] = 0;
    pq.push({0,src});

    while(!pq.empty()){

        iPair temp = pq.top();
        pq.pop();

        int u = temp.second;
        ll w = temp.first;
        if(dist[u] < w)
            continue;

        for(auto [v,curWeight] : adj[u])
        {
            // int v = x.first;
            // int curWeight = x.second;

            if(dist[v] > dist[u] + curWeight){
                dist[v] = dist[u] + curWeight;
                pq.push({w + curWeight , v});
            }
        }

    }

    return dist;

}


void  addEdge(vector<iPair> adj[] , int src , int des , int w){
    adj[src].push_back(make_pair(des , w));
    adj[des].push_back(make_pair(src,w));
}

int main()
{
    int v = 9;

    vector<iPair> adj[v];

     addEdge(adj, 0, 1, 4);
    addEdge(adj, 0, 7, 8);
    addEdge(adj, 1, 2, 8);
    addEdge(adj, 1, 7, 11);
    addEdge(adj, 2, 3, 7);
    addEdge(adj, 2, 8, 2);
    addEdge(adj, 2, 5, 4);
    addEdge(adj, 3, 4, 9);
    addEdge(adj, 3, 5, 14);
    addEdge(adj, 4, 5, 10);
    addEdge(adj, 5, 6, 2);
    addEdge(adj, 6, 7, 1);
    addEdge(adj, 6, 8, 6);
    addEdge(adj, 7, 8, 7);

    pritGraph(adj , v);

    dijkstraAlgorithm(adj , v , 0);
    return 0;
}