training/DistanceInGraphDijkstra.cpp at master · SergeyRyabinin/training · 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <memory>
#include <vector>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <regex>
#include <functional>
#include <fstream>
#include <assert.h>
#include <stack>
#include <queue>
#include <functional>

#if !defined(INT_MAX)
#define INT_MAX (0xFFFFFFFF - 1)/2
#endif

// Just a Dijkstra algorithm implementation

auto compare = [](const std::pair<unsigned int, int>& left, const std::pair<unsigned int, int>& right)
{
    return left.second > right.second;
};

class graph_t : public std::unordered_map<
    unsigned int,
    std::vector<std::pair<unsigned int, int>
    >
>
{
public:
    void addEdge(unsigned int src, unsigned int dst, int cost)
    {
        (*this)[src].push_back({ dst,cost });
        //std::push_heap((*this)[src].begin(), (*this)[src].end(), compare);
        (*this)[dst].push_back({ src,cost });
        //std::push_heap((*this)[dst].begin(), (*this)[dst].end(), compare);
    }

    void make_heap()
    {
        //O(V * 3E)
        for (auto& node : (*this))
        {
            std::make_heap(node.second.begin(), node.second.end(), compare);
        }
    }
};

int main()
{
    graph_t graph;

    graph.addEdge(1, 2, 7);
    graph.addEdge(1, 3, 9);
    graph.addEdge(1, 6, 14);

    graph.addEdge(2, 3, 10);
    graph.addEdge(2, 4, 15);

    graph.addEdge(3, 6, 2);
    graph.addEdge(3, 4, 11);

    graph.addEdge(4, 5, 6);

    graph.addEdge(5, 6, 9);

    graph.make_heap();

    //distance from queried vertex to all others
    std::vector<unsigned int> dist(graph.size(), INT_MAX);
    std::vector<int> path(graph.size());
    std::unordered_set<unsigned int> visited;

    unsigned int node = 1;
    dist[node - 1] = 0;
    while (visited.size() != graph.size())
    {
        for(size_t i = 0; i < graph[node].size(); ++i)
        {
            std::pop_heap(graph[node].begin(), graph[node].end() - i, compare);
            const auto& edge = *(graph[node].end() - i - 1);

            if (visited.find(edge.first) != visited.end())
                continue;

            if (dist[edge.first - 1] > dist[node - 1] + edge.second)
            {
                dist[edge.first - 1] = dist[node - 1] + edge.second;
                path[edge.first - 1] = node;
            }
        }

        visited.insert(node);

        int min_price = INT_MAX;
        int min_idx = 0;
        for (size_t i = 1; i < dist.size() + 1; ++i)
        {
            if (visited.find(i) == visited.end() &&
                dist[i - 1] < std::min(INT_MAX, min_price))
            {
                min_price = dist[i - 1];
                min_idx = i;
            }
        }
        if (visited.size() != graph.size())
        {
            assert(min_idx != 0);
        }
        node = min_idx;
    }

    return 0;

}