图论研究算法问题-最短路径、Dijkstra算法及C语言/C++代码实现

1.什么是最短路径

最短路径问题是图论研究中的经典算法。该问题旨在找到图中（由节点和路径组成）中两个节点之间的最短路径。大致可以分为以下几类问题。无论问题如何分类，其本质思想都没有改变：求两点之间的最短距离。

a) 从起点确定最短路径的问题——即给定起始节点求最短路径的问题。

b) 确定到终点的最短路径问题 - 与确定起点问题不同，该问题是在给定终点节点的情况下找到最短路径。在无向图中，这个问题完全等价于确定起点的问题。在有向图中，这个问题等价于通过反转所有路径的方向来确定起点的问题。

c) 确定从起点到终点的最短路径的问题——即给定起点和终点，求两个节点之间的最短路径。

d) 全局最短路径问题 - 找到图中的所有最短路径。

2。 Dijkstra算法简介

如上图所示，Dijkstra算法的核心思想是：

1）指定一个节点，比如我们要计算‘A’到其他节点的最短距离。路径

2）引入两个集合（S，U），S集合包含找到的最短路径的点（以及对应的最短长度），U集合包含最短路径没有找到的点（和A到该点的路径。注意，如上图所示，A->C最初是∞，因为没有直接相连）

3）初始化两个集合。 S-set 初始只有要计算的节点，A->A = 0 ,

4) U-set 初始为 A->B = 4, A->C = ∞, A->D = 2、A->E = ∞

5) 求U-set的路径 将最短点添加到S-set中，例如A->D = 2

6) 对U-set进行工作-path at, if ( '从 D 到 B、C、E 的距离' + 'AD 距离' 7) 重复步骤 4 和 5，直到移动结束，求出从A到其他节点的最短路径

3。示例代码

代码仅供参考