从s点到e点的最短路线用Dijkstra算法怎么写

Dijkstra算法是一种用于计算单源最短路径的贪心算法。以下是从s点到e点的最短路线用Dijkstra算法的基本过程：

1. 创建一个空的距离列表dist[]，将所有节点的距离初始化为无穷大，将起始节点s的距离设置为0。

2. 创建一个空的已访问列表visited[]。

3. 重复以下步骤，直到所有节点都被访问：

a. 从dist[]列表中选择距离最小的未访问节点u。

b. 将节点u添加到visited[]列表中。

c. 对于与节点u相邻的所有未访问节点v，如果从起始节点s到节点v的路径经过节点u的距离比当前计算出来的距离小，则更新节点v的距离值为新的距离值，并将节点u作为节点v的前驱节点。

4. 当所有节点都被访问后，我们可以通过回溯前驱节点来得到从起始节点s到目标节点e的最短路径。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

#define INF INT_MAX

// 节点类，包含节点的编号和距离起点的距离
class Node {
public:
    int id;
    int dist;

    Node(int id, int dist) {
        this->id = id;
        this->dist = dist;
    }
};

// 重载比较运算符，用于优先队列中节点的排序
class CompareNode {
public:
    bool operator() (const Node& n1, const Node& n2) {
        return n1.dist > n2.dist;
    }
};

// Dijkstra算法求解最短路径
void dijkstra(vector<vector<int>>& graph, int start, int end) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    vector<int> prev(n, -1);

    // 将起始节点加入到已访问列表中，并设置距离为0
    dist[start] = 0;

    // 创建一个优先队列，用于选择距离最小的未访问节点
    priority_queue<Node, vector<Node>, CompareNode> pq;
    pq.push(Node(start, 0));

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        // 如果当前节点已经被访问过，则忽略
        if (visited[curr.id]) {
            continue;
        }

        // 将当前节点加入到已访问列表中
        visited[curr.id] = true;

        // 如果当前节点为终点，则跳出循环
        if (curr.id == end) {
            break;
        }

        // 遍历当前节点的邻接节点，并更新它们的距离值
        for (int j = 0; j < n; j++) {
            if (graph[curr.id][j] > 0 && !visited[j]) {
                int newDist = curr.dist + graph[curr.id][j];
                if (newDist < dist[j]) {
                    dist[j] = newDist;
                    prev[j] = curr.id;
                    pq.push(Node(j, newDist));
                }
            }
        }
    }

    // 输出最短路径
    cout << "Shortest path from " << start << " to " << end << ": ";
    if (dist[end] == INF) {
        cout << "No path exists" << endl;
    } else {
        vector<int> path;
        int curr = end;
        while (curr != -1) {
            path.push_back(curr);
            curr = prev[curr];
        }
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << path[i] << " ";
        }
        cout << "(distance = " << dist[end] << ")" << endl;
    }
}

int main() {
    // 创建一个有向加权图
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {0, 0, 1, 4, 2},
        {0, 0, 0, 0, 3},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 3, 0}
    };

    // 求解最短路径
    dijkstra(graph, 0, 4);

    return 0;
}