Next Topic

单源次短路径(second_shortest_paths)

数据结构与算法第五章图(gragh) 单源次短路径(second_shortest_paths)

组别:提高组
难度:7

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

算法思路

要找到单源次短路，可以使用如下思路：

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

代码一：

/**************************************************************** 
 * 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;
}

方法二：标记法

/**************************************************************** 
 * 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;
}

Previous Topic

Back to Lesson

Next Topic