Dijkstra算法原理及其C实现详解，能否改写为一个长尾词？

本文共计1953个文字，预计阅读时间需要8分钟。

目录+什么是最短路径问题+Dijkstra算法+实现思路+案例分析+代码实现+什么是最短路径问题+如果从图中某一点（称为源点）到另一点（称为终点）的路径可能不止一条，如何找到一条一

目录

• 什么是最短路径问题
• Dijkstra算法
• 实现思路
• 案例分析
• 代码实现

什么是最短路径问题

如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

单源最短路径问题是指对于给定的图G=(V,E)，求源点v₀到其它顶点v_t的最短路径。

Dijkstra算法

Dijkstra算法用于计算一个节点到其他节点的最短路径。Dijkstra是一种按路径长度递增的顺序逐步产生最短路径的方法，是一种贪婪算法。

Dijkstra算法的核心思想是首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v₀到其它各顶点的最短路径全部求出为止。

具体来说：图中所有顶点分成两组，第一组是已确定最短路径的顶点，初始只包含一个源点，记为集合S；第二组是尚未确定最短路径的顶点，记为集合U。

按最短路径长度递增的顺序逐个把U中的顶点加到S中去，同时动态更新U集合中源点到各个顶点的最短距离，直至所有顶点都包括到S中。