交通工程Python最短路算法求换乘次数

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
#include <iomanip>
#include <algorithm>

using namespace std;

// 无向图
unordered_map<char, vector<pair<char, int>>> graph = {
    {'A', {{'B', 5}, {'C', 8}}},
    {'B', {{'A', 5}, {'C', 2}, {'D', 11}, {'E', 100}}},
    {'C', {{'A', 8}, {'B', 2}, {'E', 7}}},
    {'D', {{'B', 11}, {'F', 9}, {'E', 4}}},
    {'E', {{'B', 100}, {'C', 7}, {'D', 4}, {'F', 8}}},
    {'F', {{'D', 9}, {'E', 8}}}
};

// 打印距离表的辅助函数
void printDistances(const unordered_map<char, int>& distances) {
    cout << "当前距离表: ";
    for (const auto& entry : distances) {
        char node = entry.first;
        int dist = entry.second;
        if (dist == numeric_limits<int>::max()) {
            cout << node << ":∞ ";
        } else {
            cout << node << ":" << dist << " ";
        }
    }
    cout << endl;
}

// Dijkstra算法
void dijkstra(char start, char end) {
    // 初始化距离表
    unordered_map<char, int> distances;
    for (const auto& entry : graph) {
        char node = entry.first;
        distances[node] = numeric_limits<int>::max();
    }
    distances[start] = 0;

    // 优先队列（最小堆），存储(距离, 节点)
    priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
    pq.push({0, start});

    // 记录前驱节点用于重建路径
    unordered_map<char, char> previous;

    cout << "开始计算...." << endl;
    int step = 1;

    while (!pq.empty()) {
        // 取出当前距离最小的节点
        pair<int, char> top = pq.top();
        int current_dist = top.first;
        char current_node = top.second;
        pq.pop();

        cout << "\n步骤 " << step++ << ": 处理节点 " << current_node 
             << " (距离=" << current_dist << ")" << endl;

        // 如果已经处理过该节点（有更短路径），则跳过
        if (current_dist > distances[current_node]) {
            cout << "  跳过，已有更短路径 " << distances[current_node] << endl;
            continue;
        }

        // 遍历所有邻居
        for (const auto& edge : graph[current_node]) {
            char neighbor = edge.first;
            int weight = edge.second;
            int new_dist = current_dist + weight;
            cout << "  检查 " << current_node << "→" << neighbor 
                 << " (权重=" << weight << "), 新距离=" << new_dist;

            // 如果找到更短路径
            if (new_dist < distances[neighbor]) {
                distances[neighbor] = new_dist;
                previous[neighbor] = current_node;
                pq.push({new_dist, neighbor});
                cout << " 更新" << endl;
            } else {
                cout << " 保持原距离" << endl;
            }
        }

        printDistances(distances);

        // 如果到达终点，可以提前终止
        if (current_node == end) {
            cout << ">> 到达终点 " << end << "，算法终止 <<" << endl;
            break;
        }
    }

    // 输出最终结果
    cout << "\n最终结果:" << endl;
    cout << "从 " << start << " 到各节点的最短距离:" << endl;
    for (const auto& entry : distances) {
        char node = entry.first;
        int dist = entry.second;
        cout << "  " << node << ": " << (dist == numeric_limits<int>::max() ? "∞" : to_string(dist)) << endl;
    }

    // 重建路径
    if (distances[end] != numeric_limits<int>::max()) {
        cout << "\n最短路径 " << start << "→" << end << " (距离=" << distances[end] << "): ";
        vector<char> path;
        for (char at = end; at != start; at = previous[at]) {
            path.push_back(at);
        }
        path.push_back(start);
        reverse(path.begin(), path.end());
        for (size_t i = 0; i < path.size(); ++i) {
            if (i != 0) cout << "→";
            cout << path[i];
        }
        cout << endl;
    } else {
        cout << "\n无法到达节点 " << end << endl;
    }
}

int main() {
    // 计算从A到F的最短路径
    dijkstra('A', 'F');
    return 0;
}

import networkx as nx

# 构建无向图（两种方法共用同一个图）
G = nx.Graph()
edges = [
    ('A', 'B', 5), ('A', 'C', 8), ('B', 'C', 2),
    ('B', 'D', 11), ('B', 'E', 100), ('C', 'E', 7),
    ('D', 'E', 4), ('D', 'F', 9), ('E', 'F', 8)
]
G.add_weighted_edges_from(edges)

# 法1：Dijkstra算法
print("\n法1：nx.dijkstra_path")
def calc_short(G, start, end):
    if start == end:
        return 0, [start], True
    try:
        path = nx.dijkstra_path(G, start, end, weight='weight')
        dist = nx.dijkstra_path_length(G, start, end, weight='weight')
        return dist, path, True
    except nx.NetworkXNoPath:
        return float('inf'), [], False

distance, path, success = calc_short(G, 'A', 'F')
if success:
    print(f"最短路径: {' → '.join(path)}")
    print(f"最短距离: {distance}")
else:
    print("无法到达目标节点")

# 法2：使用更通用的networkx函数
print("法2：nx.shortest_path")
try:
    dist = nx.shortest_path_length(G, 'A', 'F', weight='weight')
    path = nx.shortest_path(G, 'A', 'F', weight='weight')
    print(f"最短路径: {' → '.join(path)}")
    print(f"最短距离: {dist}")
except nx.NetworkXNoPath:
    print("节点不可达")

import networkx as nx

# 初始化图
G = nx.Graph()

# 修正后的线路数据
line_data = {
    "L1": [("A", 5), ("B", 6), ("X", 2), ("C", 7), ("D", None)],
    "L2": [("E", 3), ("B", 6), ("F", 6), ("G", None)],
    "L3": [("H", 7), ("F", 8), ("I", None)],
    "L4": [("K", 4), ("F", 2), ("C", 5), ("N", 2), ("J", None)],
    "L5": [("M", 1), ("N", 3), ("O", 4), ("P", None)],
    "L6": [("Q", 3), ("O", 6), ("R", None)],
}

# 添加边
for line, stations in line_data.items():
    for i in range(len(stations) - 1):
        station, dist = stations[i]
        next_station, _ = stations[i + 1]
        if dist is not None:
            G.add_edge(station, next_station, weight=dist, line=line)

# 计算换乘次数（核心）
def calculate_transfers(G, path):
    if len(path) <= 1:
        return 0
    transfers = 0
    prev_line = None
    for i in range(len(path) - 1):
        u, v = path[i], path[i + 1]
        edge_data = G.get_edge_data(u, v)
        current_line = edge_data['line']
        if prev_line is not None and current_line != prev_line:
            transfers += 1
        prev_line = current_line
    return transfers

# 计算 X 到所有站点的最短路径和换乘次数
start = "X"
results = {}
for station in G.nodes():
    if station == start:
        continue
    try:
        path = nx.dijkstra_path(G, start, station, weight='weight')
        distance = nx.dijkstra_path_length(G, start, station, weight='weight')
        transfers = calculate_transfers(G, path)
        results[station] = {"distance": distance, "transfers": transfers}
    except nx.NetworkXNoPath:
        results[station] = {"distance": float('inf'), "transfers": -1}

# 输出结果
print(f"从 {start} 出发到各站的最短距离和换乘次数：")
print("{:<5} {:<10} {:<10}".format("站点", "距离", "换乘次数"))
for station, data in sorted(results.items()):
    print("{:<5} {:<10} {:<10}".format(
        station, 
        data["distance"] if data["distance"] != float('inf') else "不可达",
        data["transfers"] if data["transfers"] != -1 else "不可达"
    ))