单源次短路径(second_shortest_paths)

组别:提高组
难度:7

“单源次短路”是指从图中的一个源节点出发到达所有其他节点的次短路径(即第二短路径)。这是一个常见的问题,尤其是在有向图和加权图中。当寻找一条次短路径时,要求该路径的长度是仅次于最短路径的长度。

算法思路

要找到单源次短路,可以使用如下思路:

  1. 使用两次Dijkstra算法
    • 第一次运行Dijkstra算法,求出从源节点到所有其他节点的最短路径,并记录每个节点的最短路径长度。
    • 然后,在第二次运行Dijkstra算法时,修改路径的选择条件,允许经过一个与最短路径不同的边,进而找到从源节点到其他节点的次短路径。
  2. 标记法
    • 在Dijkstra的基础上,记录到达每个节点的最短路径和次短路径。当更新一个节点的距离时,如果新路径比记录的次短路径更短但比最短路径长,则更新次短路径。

代码一:

  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
/**************************************************************** 
 * Description: 单源次短路径  运行多次Dijkstra
 * Author: Alex Li
 * Date: 2024-08-13 11:42:34
 * LastEditTime: 2024-08-13 11:44:39
****************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

struct Edge {
    int to, cost;
};

typedef pair<int, int> P; // first: 距离, second: 节点编号

// 标准的Dijkstra算法,用于找到最短路径
vector<int> dijkstra(int n, int source, vector<vector<Edge>>& graph) {
    vector<int> dist(n, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    
    dist[source] = 0;
    pq.push({0, source});
    
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int d = p.first, u = p.second;
        
        if (dist[u] < d) continue;
        
        for (Edge e : graph[u]) {
            if (dist[u] + e.cost < dist[e.to]) {
                dist[e.to] = dist[u] + e.cost;
                pq.push({dist[e.to], e.to});
            }
        }
    }
    
    return dist;
}

// 找到次短路径的方法
int findSecondShortestPath(int n, int source, int destination, vector<vector<Edge>>& graph) {
    // 第一步:找到所有节点的最短路径
    vector<int> shortest_dist = dijkstra(n, source, graph);
    
    int second_shortest = INF;
    
    // 第二步:尝试忽略掉每条最短路径中的边
    for (int u = 0; u < n; ++u) {
        for (Edge e : graph[u]) {
            if (shortest_dist[u] + e.cost == shortest_dist[e.to]) {
                // 假如忽略此边
                int original_cost = e.cost;
                e.cost = INF; // 假装删除这条边
                
                // 运行Dijkstra寻找新路径
                vector<int> new_dist = dijkstra(n, source, graph);
                
                if (new_dist[destination] < second_shortest) {
                    second_shortest = new_dist[destination];
                }
                
                e.cost = original_cost; // 恢复边的权重
            }
        }
    }
    
    return second_shortest;
}

int main() {
    int n = 5;
    vector<vector<Edge>> graph(n);
    
    // 添加边 (节点编号从0开始)
    graph[0].push_back({1, 10});
    graph[1].push_back({2, 20});
    graph[2].push_back({3, 30});
    graph[3].push_back({4, 40});
    graph[0].push_back({2, 50});
    
    int source = 0, destination = 4;
    int second_shortest_path = findSecondShortestPath(n, source, destination, graph);
    
    cout << "从节点 " << source << " 到节点 " << destination << " 的次短路径: ";
    if (second_shortest_path == INF) {
        cout << "不存在" << endl;
    } else {
        cout << second_shortest_path << endl;
    }
    
    return 0;
}

方法二:标记法

 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
/**************************************************************** 
 * Description: 
 dist1和dist2分别记录从源节点到其他节点的最短路径和次短路径的距离。
优先队列pq用于按距离从小到大处理节点。
通过逐步松弛(relax)每个节点的邻居节点来更新路径长度。
最后,second_shortest_paths中存储了从源节点到其他节点的次短路径。
 * Author: Alex Li
 * Date: 2024-08-13 11:47:12
 * LastEditTime: 2024-08-13 11:47:26
****************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

// 定义图结构
struct Edge {
    int to, cost;
};

typedef pair<int, int> P; // first: 距离, second: 节点编号

vector<int> dijkstra_second_shortest(int n, int source, vector<vector<Edge>>& graph) {
    vector<int> dist1(n, INF), dist2(n, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    
    dist1[source] = 0;
    pq.push({0, source});
    
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int d = p.first, u = p.second;
        
        if (dist2[u] < d) continue; // 如果已经找到次短路径,跳过
        
        for (Edge e : graph[u]) {
            int new_dist = d + e.cost;
            
            if (new_dist < dist1[e.to]) {
                // 如果找到更短的路径
                swap(dist1[e.to], new_dist);
                pq.push({dist1[e.to], e.to});
            }
            
            if (new_dist > dist1[e.to] && new_dist < dist2[e.to]) {
                // 如果找到次短路径
                dist2[e.to] = new_dist;
                pq.push({dist2[e.to], e.to});
            }
        }
    }
    
    return dist2;
}

int main() {
    int n = 5;
    vector<vector<Edge>> graph(n);
    
    // 添加边 (节点编号从0开始)
    graph[0].push_back({1, 10});
    graph[1].push_back({2, 20});
    graph[2].push_back({3, 30});
    graph[3].push_back({4, 40});
    graph[0].push_back({2, 50});
    
    int source = 0;
    vector<int> second_shortest_paths = dijkstra_second_shortest(n, source, graph);
    
    for (int i = 0; i < n; i++) {
        cout << "从节点 " << source << " 到节点 " << i << " 的次短路径: ";
        if (second_shortest_paths[i] == INF) {
            cout << "不存在" << endl;
        } else {
            cout << second_shortest_paths[i] << endl;
        }
    }
    
    return 0;
}
Scroll to Top