Dijkstra算法 举例
时间: 2023-11-05 19:26:38 浏览: 38
Dijkstra算法是一种用于求解最短路径的算法,以下是一个简单的例子:
假设有以下图形:
![image](https://cdn.luogu.com.cn/upload/image_hosting/f1vz8z5t.png)
我们想要求出节点A到其他节点的最短路径。
首先,我们将A标记为起点,并将A到各个节点的距离初始化为无穷大(除了A到A的距离为0):
![image](https://cdn.luogu.com.cn/upload/image_hosting/4g5l8f8l.png)
接下来,我们从未标记的节点中选择距离A最近的节点,也就是B。将B标记为已访问,并更新A到B相邻节点的距离:
![image](https://cdn.luogu.com.cn/upload/image_hosting/7t9lkl58.png)
接着,我们再次从未标记的节点中选择距离A最近的节点,也就是C。将C标记为已访问,并更新A到C相邻节点的距离:
![image](https://cdn.luogu.com.cn/upload/image_hosting/3xgv6i2l.png)
继续这个过程,直到所有节点都被标记为已访问。最后的结果如下:
![image](https://cdn.luogu.com.cn/upload/image_hosting/1h3z39r0.png)
因此,A到各个节点的最短路径分别为:
- A到B的最短路径为2,路径为A->B
- A到C的最短路径为4,路径为A->B->C
- A到D的最短路径为5,路径为A->B->D
- A到E的最短路径为6,路径为A->B->D->E
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)