Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar12 / Dijkstra.cpp
blob: 3ce9de281bdb46e540c5986897175067c05116bf (plain) (blame)
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
#include"../Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h"
#include<queue>
#include<iostream>
#include<list>

using vertex_t = MatrixGraph::vertex_t;
using weight_t = MatrixGraph::weight_t;

bool relax(std::vector<weight_t>& distance, const MatrixGraph& g, vertex_t reached, vertex_t currentVertex) {
    if (distance[reached] > distance[currentVertex] + g.getWeight(currentVertex, reached)) {
        distance[reached] = distance[currentVertex] + g.getWeight(currentVertex, reached);
        return true;
    }
    return false;
}

// Намиране на най - къс път между два върха
int Dijkstra(const MatrixGraph& g, vertex_t start, vertex_t end) {
    std::vector<vertex_t> parent(g.vertexCount(), -1);
    std::vector<weight_t> distances(g.vertexCount(), INT_MAX);

    struct VertexDistancePair {
        vertex_t vertex;
        weight_t distanceFromStart;

        bool operator<(const VertexDistancePair& other) const {
            return distanceFromStart > other.distanceFromStart;
        }
    };

    std::priority_queue<VertexDistancePair> q;

    distances[start] = 0;
    q.push({ start, 0 });

    while (!q.empty()) {
        auto currentPair = q.top();
        q.pop();

        if (currentPair.vertex == end) {
            auto currentVertex = currentPair.vertex;

            std::list<vertex_t> path;

            while (currentVertex != start) {
                path.insert(path.begin(), currentVertex);
                currentVertex = parent[currentVertex];
            }

            path.insert(path.begin(), start);

            for (const auto& v : path)
                std::cout << v << std::endl;

            return distances[currentPair.vertex];
        }

        const auto& adjacent = g.adjacent(currentPair.vertex);

        for (auto reached : adjacent) {
            if (relax(distances, g, reached, currentPair.vertex)) {
                parent[reached] = currentPair.vertex;
                q.push({ reached, distances[reached] });
            }
        }
    }

    return INT_MAX;
}

int main() {
    MatrixGraph g(8);

    g.addEdge(0, 1, 23);
    g.addEdge(0, 2, 74);
    g.addEdge(0, 3, 24);

    g.addEdge(1, 2, 35);
    g.addEdge(1, 4, 23);

    g.addEdge(2, 4, 24);
    g.addEdge(2, 3, 26);

    g.addEdge(3, 6, 32);

    g.addEdge(4, 5, 51);
    g.addEdge(4, 7, 17);

    g.addEdge(5, 7, 15);

    g.addEdge(6, 7, 32);


    int sp = Dijkstra(g, 0, 7);

    std::cout << std::endl << sp;
}