请详细介绍dijkstra算法的原理以及代码实现

Dijkstra算法的基本思想是通过逐步扩展离起点最近的节点来找到从起点到其他各点的最短路径[^1]。其工作流程包括以下几个关键步骤：

1. 初始化：设置起点的距离为0，其他所有节点的距离设为无穷大（通常使用特殊值如INT_MAX）。将起点标记为已访问。

2. 选择未访问的最小距离节点：在这个阶段，总是选择具有最小距离估计值的节点。

3. 更新邻居节点的距离：对于当前选中的节点，检查它到相邻节点的边。如果经过这个边到达相邻节点的距离比已知的更短，就更新其距离。

4. 标记节点为已访问：完成上述操作后，将当前节点标记为已访问，防止重复计算。

5. 重复步骤2至4，直到所有节点都被访问或找到终点。

以下是一个简单的MATLAB实现示例：

function shortestPath = dijkstra(graph, startNode)
    % 初始化
    distances = Inf(size(graph.vertices));
    distances(startNode) = 0;
    visited = false(size(graph.vertices), 1);
    
    while ~all(visited)
        % 找到未访问的最小距离节点
        [minDistance, minIndex] = min(distances(~visited));
        
        % 如果已经找到终点，则跳出循环
        if minIndex == graph.vertices(end)
            break;
        end
        
        visited(minIndex) = true; % 标记节点为已访问
        
        % 更新邻接节点的距离
        for neighbor = graph.neighbors(minIndex)
            newDistance = distances(minIndex) + graph.weights(minIndex, neighbor);
            if newDistance < distances(neighbor)
                distances(neighbor) = newDistance;
            end
        end
    end
    
    shortestPath = distances;
end

而对于C++版本[^2]，这里给出基本框架：

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

class Graph {
public:
    // ...定义图的结构和相关函数...
};

std::vector<int> dijkstra(Graph& graph, int startNode) {
    // 初始化距离向量和优先级队列
    std::vector<int> distances(graph.getNumVertices(), INT_MAX);
    distances[startNode] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    // ...按照Dijkstra算法的逻辑填充代码...

    return distances;
}