多源最短路径#include <bits/stdc++.h> using namespace std;

多源最短路径是指从图中的每个顶点到其他所有顶点的最短路径。下面是一个使用Dijkstra算法求解多源最短路径的示例代码：

#include <bits/stdc++.h>
using namespace std;

#define INF INT_MAX // 定义无穷大

// 使用Dijkstra算法求解多源最短路径
void dijkstra(vector<vector<int>>& graph, int src) {
    int n = graph.size(); // 图的顶点数

    // 创建一个数组dist，用于存储从源点到其他顶点的最短距离
    vector<int> dist(n, INF);
    dist[src] = 0; // 源点到自身的距离为0

    // 创建一个优先队列，用于选择距离最小的顶点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, src));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        // 遍历u的邻接顶点
        for (int v = 0; v < n; v++) {
            // 如果存在从u到v的边，并且通过u可以获得更短的距离
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // 输出最短距离
    for (int i = 0; i < n; i++) {
        cout << "从顶点" << src << "到顶点" << i << "的最短距离为：" << dist[i] << endl;
    }
}

int main() {
    int n = 5; // 图的顶点数

    // 创建一个邻接矩阵表示的图
    vector<vector<int>> graph(n, vector<int>(n,0));
    graph[0][1] = 10;
    graph[0][4] = 5;
    graph[1][2] = 1;
    graph[1][4] = 2;
    graph[2][3] = 4;
    graph[3][2] = 6;
    graph[3][0] = 7;
    graph[4][1] = 3;
    graph[4][2] = 9;
    graph[4][3] = 2;

    // 从每个顶点开始求解最短路径
    for (int i = 0; i < n; i++) {
        dijkstra(graph, i);
    }

    return 0;
}

这段代码使用了邻接矩阵来表示图，其中0表示两个顶点之间没有边，其他非零值表示边的权重。通过调用`dijkstra`函数，可以从每个顶点开始求解最短路径，并输出结果。