dijikstra 模板

当然，我可以为您提供一个Dijkstra算法的模板。以下是一个使用C++实现的基本示例：

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

using namespace std;

// 定义图的邻接矩阵表示
#define INF INT_MAX
typedef vector<vector<int>> Graph;

vector<int> Dijkstra(const Graph& graph, int source) {
    int n = graph.size(); // 图中节点的数量

    // 创建一个距离数组，并将所有距离初始化为无穷大
    vector<int> dist(n, INF);
    dist[source] = 0; // 将源节点的距离初始化为0

    // 创建一个优先级队列（最小堆）来保存当前最短路径的节点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source}); // 将源节点加入优先级队列

    while (!pq.empty()) {
        int u = pq.top().second; // 当前最短路径的节点
        pq.pop();

        // 遍历当前节点的所有邻居
        for (int v = 0; v < n; ++v) {
            // 如果存在一条边从u到v，并且通过u到达v的距离更短
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]; // 更新最短路径距离
                pq.push({dist[v], v}); // 将邻居节点加入优先级队列
            }
        }
    }

    return dist; // 返回源节点到各个节点的最短路径距离数组
}

int main() {
    int n = 5; // 图中节点的数量
    Graph graph(n, vector<int>(n, 0)); // 初始化图的邻接矩阵

    // 添加图的边（示例）
    graph = 2;
    graph = 4;
    graph = 1;
    graph = 7;
    graph = 3;
    graph = 2;

    int source = 0; // 源节点

    vector<int> shortestDistances = Dijkstra(graph, source); // 使用Dijkstra算法计算最短路径

    // 输出源节点到各个节点的最短路径距离
    cout << "Shortest distances from source node " << source << ":" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "Node " << i << ": " << shortestDistances[i] << endl;
    }

    return 0;
}

这是一个简单的Dijkstra算法模板，用于计算从源节点到图中所有其他节点的最短路径距离。您可以根据自己的需要进行修改和扩展。希望对您有所帮助！