最短路径

  • Dijkstra
    可以找到一个点到其他所有点的最短距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef pair<int, int> pii;
vector<int> dist(n, -1);
vector<bool> visited(n);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({start, 0});
while(!pq.empty()){
    int u = pq.top().first;
    int current_dist = pq.top().second;
    pq.pop();
    if(visited[u]) continue;
    visited[u] = true;
    for(int v = 0; v < n; v++){
        if(path[u][v] != -1){
            int weight = path[u][v];
            if(dist[u] + weight < dist[v]){
                dist[v] = dist[u] + weight;
                pq.push({v, dist[v]});
            }
        }
    }
}
  • floyd
    可以找到所有点之间的最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> dist(n, vector<int>(n, -1));
vector<vector<int>> path(n, vector<int>(n, -1));
for(int i = 0; i < n; i++){
    dist[i][i] = 0;
}
for (int k = 0; k < n; k++) {     
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][k] != -1 && dist[k][j] != -1) {
                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k; 
                }
            }
        }
    }
}