dijkstra邻接表_最短路径问题——迪杰斯特拉算法(Dijkstra)

迪杰斯特拉算法(Dijkstra)是一种贪心算法，用于解决最短路径问题。它可以处理有权有向图或无向图，但不允许有负权边（权重必须为非负数）。

算法思路：

1. 从起点开始，初始化所有节点的距离为无穷大，起点距离为0；

2. 将起点加入“已访问”集合；

3. 对于起点的所有邻居节点，更新它们的距离（如果通过当前节点到达邻居节点的距离小于邻居节点原有的距离，则更新邻居节点的距离）；

4. 从未访问集合中选择距离起点最近的节点，加入“已访问”集合；

5. 重复步骤3和4，直到所有节点都被加入“已访问”集合或者没有与起点相连的节点。

算法实现：

Dijkstra算法的实现通常使用优先队列（PriorityQueue）来维护未访问集合中距离起点最近的节点。具体实现步骤如下：

1. 创建一个空的优先队列Q，将起点加入Q中，并设置起点到自身的距离为0；

2. 创建一个数组dist[]，用于保存起点到各个节点的距离，初始化为无穷大；

3. 创建一个数组visited[]，用于标记节点是否被访问过，初始化为false；

4. 将dist[起点]的值设置为0；

5. 当Q不为空时，重复以下步骤：

a. 从Q中取出距离起点最近的节点u；

b. 如果节点u已经被访问过，则跳过此次循环；

c. 将节点u标记为已访问；

d. 对于节点u的每个邻居节点v，如果节点v未被访问过并且通过节点u到达节点v的距离小于dist[v]，则更新dist[v]的值；

e. 将节点v加入Q中。

6. 最终，dist数组中保存的就是起点到各个节点的最短距离。

Dijkstra算法的时间复杂度为O(ElogV)，其中E为边数，V为节点数。这是因为算法需要对每个节点的所有邻居节点进行遍历，而优先队列的插入和删除操作的时间复杂度为O(logV)。