武汉地铁站点最短路径搜索的实现（一）——Dijkstra算法（C++ coding）

好的，以下是基于 Dijkstra 算法实现武汉地铁站点最短路径搜索的 C++ 代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 100; // 最大站点数
const int INF = INT_MAX; // 无穷大

vector<pair<int, int>> adj[MAXN]; // 邻接表存图
int dist[MAXN]; // 距离数组
bool vis[MAXN]; // 访问标记数组

// Dijkstra 算法实现
void dijkstra(int s) {
    dist[s] = 0; // 初始距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push(make_pair(dist[s], s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue; // 已经访问过了
        vis[u] = true;
        for (pair<int, int> edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w; // 更新距离
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入站点数和边数
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 输入边的起点、终点、权值
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w)); // 无向图
    }
    int s, t;
    cin >> s >> t; // 输入起点和终点
    fill(dist, dist + n, INF); // 初始化距离数组
    dijkstra(s); // Dijkstra 算法求最短路径
    cout << dist[t] << endl; // 输出起点到终点的最短距离
    return 0;
}

在代码中，我们使用邻接表存储图，并使用了 STL 中的优先队列来实现 Dijkstra 算法。同时，我们也注意到 Dijkstra 算法适用于边权值非负的图，因此在实现中需要对边权值的范围做出限制。