C++实现Dijkstra算法

前言

在计算机科学中，Dijkstra算法是一种用于在加权有向图中求解最短路径的算法。该算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）于1956年提出。Dijkstra算法在许多应用情况下都被广泛使用，包括路由导航、网络优化等。

实现Dijkstra算法

下面是一个用C++实现Dijkstra算法的示例代码：

#include 
#include 
#include 
#include 

const int INF = std::numeric_limits::max();

typedef std::pair P;  // 用于保存节点和其对应的最短路径长度

std::vector dijkstra(std::vector>& graph, int start) {
    int num_nodes = graph.size();
    std::vector dist(num_nodes, INF);  // 初始化所有节点到起点的距离为无穷大
    std::priority_queue, std::greater
> pq;  // 优先队列用于保存最短距离和节点
    
    dist[start] = 0;  // 起点到自身的距离为0
    pq.push({0, start});
    
    while (!pq.empty()) {
        P top = pq.top();
        pq.pop();
        int d = top.first;
        int u = top.second;
        
        // 如果当前节点的距离已经更新过，说明已经找到了最短路径到达该节点，可以忽略该节点
        if (dist[u] < d) {
            continue;
        }
        
        // 遍历当前节点的邻居节点，更新最短路径
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int w = neighbor.second;
            
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

int main() {
    int num_nodes = 6;  // 图的节点数
    int start = 0;  // 起点
    
    // 创建图的邻接表表示
    std::vector> graph(num_nodes);
    graph[0].push_back({1, 7});
    graph[0].push_back({2, 9});
    graph[0].push_back({5, 14});
    graph[1].push_back({2, 10});
    graph[1].push_back({3, 15});
    graph[2].push_back({3, 11});
    graph[2].push_back({5, 2});
    graph[3].push_back({4, 6});
    graph[4].push_back({5, 9});
    
    // 调用Dijkstra算法求解最短路径
    std::vector shortest_distances = dijkstra(graph, start);
    
    // 输出最短路径
    std::cout << "Shortest distances from node " << start << " to all other nodes:" << std::endl;
    for (int i = 0; i < num_nodes; i++) {
        std::cout << "Node " << i << ": " << shortest_distances[i] << std::endl;
    }
    
    return 0;
}

代码解释

首先，我们定义了一个常量INF，表示无穷大的距离。接下来，我们定义了一个P类型的别名，用于保存节点和其对应的最短路径长度。然后，我们实现了一个名为dijkstra的函数，用于执行Dijkstra算法。该函数接受一个加权有向图和起点作为参数，并返回从起点到所有其他节点的最短距离。

在函数中，我们首先初始化所有节点到起点的距离为无穷大。然后，我们使用一个优先队列来保存最短距离和节点。将起点的最短距离设置为0，并将起点和最短距离加入优先队列。之后，我们开始处理优先队列中的节点。对于每个节点，我们遍历其邻居节点，并更新最短距离。如果更新了某个邻居节点的最短距离，我们将该邻居节点和新的最短距离加入优先队列。最终，我们返回计算得到的最短距离数组。

在main函数中，我们创建了一个包含6个节点的图的邻接表表示。通过调用dijkstra函数，我们求解了从起点到所有其他节点的最短距离，并将结果输出到控制台。

总结

通过使用C++编写代码，我们成功地实现了Dijkstra算法。该算法可以用于在加权有向图中求解最短路径。我们通过构建一个邻接表来表示图，并使用优先队列来高效地处理节点。通过调用dijkstra函数，我们可以得到从起点到所有其他节点的最短距离。