图的单元最短路径算法知识点和实现思路

单元最短路径算法是一种经典的图论算法，用于求解带权有向图或无向图中两个节点之间的最短路径。常用的单元最短路径算法包括 Dijkstra 算法和 Bellman-Ford 算法。

Dijkstra 算法的实现思路如下：

1. 初始化一个距离列表，表示起点到各个节点的距离，将起点的距离设为 0，其余节点的距离设为无穷大。
2. 初始化一个集合，表示已经找到最短路径的节点集合，将起点加入该集合中。
3. 对于起点可达的节点，更新其距离列表中的距离值为起点到该节点的实际距离，如果该节点不在集合中，则加入集合中。
4. 从距离列表中选择一个未被访问过的距离最小的节点，将其加入集合中。
5. 重复步骤 3 和步骤 4，直到所有节点都被访问过或者不能到达某些节点。

Bellman-Ford 算法的实现思路如下：

1. 初始化一个距离列表，表示起点到各个节点的距离，将起点的距离设为 0，其余节点的距离设为无穷大。
2. 对于图中的每条边，重复以下过程：
a. 如果从起点到该边的起点的距离加上该边的边权小于从起点到该边的终点的距离，则更新从起点到该边的终点的距离值。
3. 重复步骤 2，直到所有边都被访问过或者存在负环路。

需要注意的是，Dijkstra 算法适用于没有负权边的图，而 Bellman-Ford 算法可以处理存在负权边的图。但是，如果图中存在负环路，则 Bellman-Ford 算法会进入死循环，因此需要在算法中加入判断负环路的代码。

实现时，可以使用优先队列来维护距离列表中距离最小的节点，并使用邻接表来存储图的信息。