Dijikstra算法流程图

### Dijkstra算法流程图

Dijkstra算法是一种用于计算加权图中单源最短路径的经典算法。该算法基于贪心策略，逐步构建起始节点到其余各顶点之间的最短路径树。

#### 图解说明

1. 初始化阶段：
- 设置初始节点S的距离为0，其他所有节点的距离设为无穷大。
- 创建一个未访问集合P，将所有节点加入其中[^2]。

2. 迭代过程：
- 从未访问过的节点中选取具有最小临时距离值的一个节点u作为当前处理对象。
- 对于每一个与u相邻接的节点v执行如下操作：
- 计算从s经过u到达v的新路径长度d(s,v)=d(s,u)+w(u,v)，这里w表示边上的权重。
- 如果新路径较原先记录的小，则更新v对应的最短路径估计值并标记前驱结点为u。
- 将已处理完毕的节点u移出待选列表P，并将其状态改为已确认(visited)。

3. 终止条件：
- 当目标节点被选定为当前节点时停止迭代；或者当不存在任何可继续探索的有效邻居时结束循环。

4. 结果输出：
- 返回由上述过程中累积得到的所有节点至原点间的最优路线及其总成本。

以下是简化版的文字描述转化为图形化表达：

graph TD;
    A[初始化] --> B{选择起点};
    B --> C[设置起点距离=0];
    C --> D[其它点距离=∞];
    D --> E[创建未访问集P];
    
    F{存在未访问？} --- G[是];
    F --- H[否, 输出结果];
    
    G --> I[取最小距离点U];
    I --> J{U有邻接V?};
    K[V∈P & 新路更优?]--> L[更新V的距离和前驱];
    M[U移出P, 加入已访];
    N[M回到F];

    J--- O[否]->M;
    J--- P[是]->K;

此Mermaid图表展示了Dijkstra算法的主要逻辑框架，有助于理解其工作原理以及每一步骤的具体含义。