hacktober2020/dijkstra_algorithm.cpp at master · anurupsdev/hacktober2020 · 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
#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Graph
{
    public:
        map<T,list<pair<T,int>>> m;
        Graph()
        {
        }
        void addedge(T u,T v,int dist,bool birid=true)
        {
            m[u].push_back(make_pair(v,dist));
            if(birid)
            {
                m[v].push_back(make_pair(u,dist));
            }
        }
        void printdijsktra()
        {

            for(auto city:m)
            {
                T cityname=city.first;
                cout<<cityname<<"->";
                for(auto citie:city.second)
                {
                    cout<<"( "<<citie.first<<" , "<<citie.second<<" )"<<endl;
                }
            }
        }
        void dijsktrasssp(T src)
        {
            map<T,int>dist;
            for(auto j:m)
            {
                dist[j.first]=INT_MAX;
            }
            set<pair<int,T>> s;
            dist[src]=0;
            s.insert(make_pair(0,src));
            while(!s.empty())
            {
                auto p=*(s.begin());
                T node=p.second;
                int nodedit=p.first;
                s.erase(s.begin());
                for(auto neigh:m[node])
                {
                    if(neigh.second+nodedit<dist[neigh.first])
                    {
                        T dest=neigh.first;
                        auto f=s.find(make_pair(dist[dest],dest));
                        if(f!=s.end())
                        {
                            s.erase(f);
                        }
                        dist[dest]=neigh.second+nodedit;
                        s.insert(make_pair(dist[dest],dest));
                    }
                }
            }
            for(auto d:dist)
            {
                cout<<d.first<<" is located at distance of "<<d.second<<endl;
            }
        }
};
int main() {
    /*Graph<int> g;
    g.addedge(1,2,1);
    g.addedge(1,3,4);
    g.addedge(2,3,1);
    g.addedge(3,4,2);
    g.addedge(1,4,7);
    //g.printdijsktra();
    g.dijsktrasssp(1);
    */
    Graph<string>india;
    india.addedge("Amritsar","Delhi",1);
    india.addedge("Amritsar","Jaipur",4);
    india.addedge("Jaipur","Delhi",2);
    india.addedge("Jaipur","Mumbai",8);
    india.addedge("Bhopal","Agra",2);
    india.addedge("Mumbai","Bhopal",3);
    india.addedge("Agra","Delhi",1);
    india.dijsktrasssp("Amritsar");
    return 0;

}