c++ 单源最短路径-狄杰斯特拉算法

• 狄杰斯特拉算法
• 适用范围:没有负权重的图, 可以有环,有向无向图均可
• 求解问题:单源最短路径
• 时间复杂度：V^2

源码

#include 
#include 
#include 
#include 

using namespace std;

struct Edge {
    int to;
    int weight;
};

struct Vertex {
    vector<Edge> adjacent;
    int dis = INT_MAX;
    int closed = 0;
    int pre = -1;
};

class Graph {
    vector<Vertex> nodes;
    int n;

public:
    Graph(int n, vector<vector<int>> &edges) : nodes(n) {
        this->n = n;
        for (auto &vec: edges) {
            int from = vec[0];
            int to = vec[1];
            int weight = vec[2];
            nodes[from].adjacent.push_back({.to = to, .weight = weight});
        }
    }

    [[nodiscard]] int Vex() const {
        return n;
    }

    vector<Edge> &getEdges(int v) {
        return nodes[v].adjacent;
    }


    void setClosed(int v) {
        nodes[v].closed = 1;
    }

    [[nodiscard]] bool isClosed(int v) const {
        return nodes[v].closed;
    }

    void setDistance(int v, int d) {
        nodes[v].dis = d;
    }

    int getDistance(int v) {
        return nodes[v].dis;
    }

    void setPre(int v, int pre) {
        nodes[v].pre = pre;
    }

    int getPre(int v) {
        return nodes[v].pre;
    }
};

/**
 *  狄杰斯特拉算法
 *  适用范围:没有负权重的图, 可以有环,有向无向图均可
 *  求解问题:单源最短路径
 *  时间复杂度：V^2
 *
 *
 * **/

class Dijkstra {
public:
    int start;
    Graph *g;

    Dijkstra(int start, Graph *g) : start(start), g(g) {}

    void print(int v) const {
        if (g->getPre(v) != -1) {
            print(g->getPre(v));
        }
        cout << v << "\t";
    }

    void print() const {
        for (int i = 0; i < g->Vex(); i++) {
            cout << i << " node:[from 0 path]" << "\t";
            print(i);
            cout << endl;
        }
    }

    void traversal() const {
        g->setDistance(start, 0);
        for (int k = 0; k < g->Vex(); k++) {
            // 在open list 里面找一个最小的
            int v = -1;
            for (int i = 0; i < g->Vex(); i++) {
                if (g->isClosed(i) || g->getDistance(i) == INT_MAX) {
                    continue;
                }
                if (v == -1 || g->getDistance(i) < g->getDistance(v)) {
                    v = i;
                }
            }
            // open list 找不到节点
            if (-1 == v) {
                break;
            }
            // 添加到close list
            g->setClosed(v);
            for (auto &adj: g->getEdges(v)) {
                int to = adj.to;
                int weight = adj.weight;
                int distance = g->getDistance(v) + weight;
                if (g->isClosed(to)) {
                    continue;
                }
                if (g->getDistance(to) > distance) {
                    g->setDistance(to, distance);
                    g->setPre(to, v);
                }
            }
        }
        print();
    }
};

int main() {
    vector<vector<int>> data = {
            {0, 1, 2},
            {1, 2, 2},
            {2, 3, 1},
            {3, 4, 2},
            {0, 4, 3},
    };
    auto g = new Graph(5, data);
    Dijkstra dj(0, g);
    dj.traversal();
}


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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

输出

c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法
c++ 单源最短路径-狄杰斯特拉算法