最优路径的算法及代码示例

假设有编号1，2，3，4，5等五个节点。1为起点，5为终点。1可以通向2，距离是3，2可以通向3距离是2，3可以通向4距离是1，4可以通向5距离是2，2可以通向5距离是8，3可以通向5距离是5。获取最优路径的算法如下：

#include 
#include 
#include 
#include 
#include 

using namespace std;

// 定义图的结构
class Graph {
public:
    // 构造函数，初始化顶点数量和邻接表
    Graph(int vertices) : V(vertices) {
        adj.resize(vertices);  // 初始化邻接表大小
    }

    // 添加带权重的边到图中
    void addEdge(int u, int v, int weight) {
        adj[u].push_back(make_pair(v, weight));  // 将边(u, v)及其权重添加到邻接表
        adj[v].push_back(make_pair(u, weight));  // 如果是有向图，则注释掉这一行
    }

    // 使用Dijkstra算法查找最短路径
    vector dijkstra(int start, int end) {
        // 初始化距离数组为无穷大
        vector dist(V, numeric_limits::max());
        // 初始化访问标记数组为false
        vector visited(V, false);
        // 初始化前驱节点数组为-1
        vector prev(V, -1);

        // 使用优先队列（最小堆）来选择当前距离最小的节点进行扩展
        priority_queue, vector>, greater>> pq;

        // 起点的距离设置为0，并将其加入优先队列
        dist[start] = 0;
        pq.push(make_pair(0, start));

        while (!pq.empty()) {
            // 取出距离最小的节点
            int u = pq.top().second;
            pq.pop();

            // 如果该节点已经被访问过，则跳过
            if (visited[u]) continue;
            visited[u] = true;  // 标记该节点为已访问

            // 遍历该节点的所有邻居节点
            for (const auto &neighbor : adj[u]) {
                int v = neighbor.first;  // 邻居节点
                int weight = neighbor.second;  // 边的权重

                // 如果邻居节点未被访问且通过当前节点到达它的距离更短
                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;  // 更新距离
                    prev[v] = u;  // 更新前驱节点
                    pq.push(make_pair(dist[v], v));  // 将邻居节点加入优先队列
                }
            }
        }

        // 构建路径
        vector path;
        // 如果终点不可达，返回空路径
        if (dist[end] == numeric_limits::max()) return path;

        // 从终点开始回溯，构建路径
        int u = end;
        while (u != -1) {
            path.push_back(u);  // 将节点加入路径
            u = prev[u];  // 回溯到前驱节点
        }

        reverse(path.begin(), path.end());  // 反转路径以得到从起点到终点的顺序
        return path;
    }

private:
    int V;  // 图的顶点数
    vector>> adj;  // 邻接表表示图，pair<目标节点, 权重>
};

int main() {
    // 创建图实例并添加带权重的边
    Graph g(5);  // 节点编号从0开始，所以需要5个节点（0-4）
    
    // 添加边及其权重
    g.addEdge(0, 1, 3);  // 1可以通向2，距离是3
    g.addEdge(1, 2, 2);  // 2可以通向3，距离是2
    g.addEdge(2, 3, 1);  // 3可以通向4，距离是1
    g.addEdge(3, 4, 2);  // 4可以通向5，距离是2
    g.addEdge(1, 4, 8);  // 2可以通向5，距离是8
    g.addEdge(2, 4, 5);  // 3可以通向5，距离是5

    int start = 0;  // 起点1对应索引0
    int end = 4;    // 终点5对应索引4

    // 查找最佳路径
    vector path = g.dijkstra(start, end);

    // 输出结果
    if (!path.empty()) {
        cout << "最佳路径: ";
        for (int node : path) {
            cout << node + 1 << " ";  // 输出节点编号时加1以匹配题目中的编号
        }
        cout << endl;
    } else {
        cout << "无法到达目标节点" << endl;
    }

    return 0;
}

运行后的输出结果为：

最佳路径: 1 2 3 4 5 

代码解释：

Graph类：

Graph(int vertices)：构造函数，初始化图的顶点数。

addEdge(int u, int v, int weight)：添加一条带权重的边。

dijkstra(int start, int end)：实现Dijkstra算法，计算从起点到终点的最短路径，并返回路径上的节点列表。

dijkstra方法：

使用优先队列（最小堆）来选择当前距离最小的节点进行扩展。

dist数组存储从起点到各节点的最短距离。

visited数组用于标记节点是否已被访问。

prev数组用于记录每个节点的前驱节点，以便在最后构建路径。

main函数：

创建图实例并添加带权重的边。

调用dijkstra方法获取从起点到终点的最佳路径，并输出结果。