dijkstra 算法过程

Dijkstra算法是一种用于计算图中从一个顶点到其他所有顶点的最短路径的算法。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出。Dijkstra算法的基本思想是通过不断更新起始顶点到其他顶点的最短路径长度，逐步找到最短路径。以下将详细介绍Dijkstra算法的步骤，并给出一个例题和表格供读者参考。

一、算法步骤

1. 初始化

- 设置起始顶点的最短路径为0，其余顶点的最短路径为无穷大。

- 将起始顶点加入已访问的顶点集合。

2. 更新

- 从未访问的顶点中选择离起始顶点最近的顶点，将其加入已访问的顶点集合。

- 更新起始顶点到其他顶点的最短路径长度，如果经过新加入的顶点到其他顶点的路径长度小于当前已知的最短路径长度，则更新最短路径长度。

3. 重复更新直到所有顶点都被访问过。

二、算法实例

为了更好地理解Dijkstra算法的具体应用步骤，我们通过一个实际的例题来演示算法的执行过程。

假设有以下带权重的图，起始顶点为A：

顶点 A B C D E

A 0 3 4 ∞ ∞

B ∞ 0 ∞ 1 7

C ∞ 4 0 2 ∞

D ∞ ∞ ∞ 0 5

E ∞ ∞ ∞ ∞ 0

表中每个元素表示从对应顶点到其它顶点的边的权重，"∞"表示没有直接相连的边。

我们按照Dijkstra算法的步骤来计算从顶点A到其他顶点的最短路径长度。

1. 初始化

起始顶点为A，初始化A到各顶点的最短路径长度为0，其余顶点的最短路径长度为∞。将A加入已访问的顶点集合。

2. 更新

选择A到B的路径长度最短，将B加入已访问的顶点集合。更新A到C和A到D的最短路径长度。

3. 重复更新

依次选择离起始顶点最近的顶点，并更新最短路径长度，直到所有顶点被访问。

通过不断的更新，最终得到从顶点A到其他顶点的最短路径长度表格如下：

. -

. 可修编. Dijkstra算法描述

目录

一、算法概述1

二、算法原理及计算1

2.1算法原理1

2.2计算过程2

2.3改良的算法〔Dijkstra-like〕分析5

三、源码分析6

四、接口调用7

一、算法概述

Dijkstra〔迪杰斯特拉〕算法是典型的单源最短路径计算算法，用于解决源点到所有结点最短路径计算的问题，它采用了分治和贪心〔动态规划的特殊形式〕的思想搜索全局最优解。

本系统采用了主流、开源的JAVA图论库——Jgrapht来解决源点到终点间所有可能路径输出的问题，它的核心计算引擎采用了一种Dijkstra-like算法，由经典的Dijkstra〔迪杰斯特拉〕算法演化和改良而来。

二、算法原理及计算

2.1算法原理

Dijkstra算法思想为：设(,)GVE是带权有向图，V代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径. -

. 可修编. 的顶点集合，用S表示〔初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点参加到集合S中〕；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个参加到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部参加到集合S中。

2.2计算过程

以图1为例讨论Dijkstra算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为①，逐步搜索，每次找出一个结点到源点①的最短路径，直至完成所有结点的计算。

- 1 - dijkstra标号法

Dijkstra标号法是一种用于解决最短路径问题的算法。该算法是由荷兰计算机科学家EdsgerW.Dijkstra在1956年提出的，被广泛应用于路由协议、网络规划、城市规划等领域。

该算法的基本思想是从一个起点开始，逐步扩展到周围的点，直到到达目标点。在这个过程中，每个点都被赋予一个标号，表示从起点到该点的最短距离。算法使用一个称为“优先队列”的数据结构来维护待扩展的点，以保证每次扩展的点都是当前距离起点最近的点。

Dijkstra标号法的具体步骤如下：

1. 初始化：将起点的标号设为0，其余点的标号设为无限大。

2. 将起点加入优先队列中。

3. 从优先队列中取出距离起点最近的点，更新与该点相邻的点的标号值。

4. 将更新后的点加入优先队列。

5. 重复步骤3和4，直到到达目标点或者优先队列为空。

6. 如果到达目标点，则返回该点的标号值，否则表示不存在从起点到目标点的路径。

Dijkstra标号法的时间复杂度为O(ElogV)，其中E表示边数，V表示点数。虽然该算法在解决最短路径问题方面表现出色，但是它不能处理带有负权边的图，因为负权边会导致优先队列的错误排序。对于带有负权边的图，应该使用另一种算法——Bellman-Ford算法。

Dijkstra算法是一种用于计算图中节点之间最短路径的经典算法。它是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发明的，是广泛应用的最短路径算法之一。

在leetcode中，有许多关于Dijkstra算法的经典例题，通过这些例题的练习可以帮助我们更深入地理解和掌握Dijkstra算法的原理和应用。本文将以leetcode上的几个典型例题为例，详细讲解Dijkstra算法的应用和实现过程，希望能够帮助读者加深对Dijkstra算法的理解，并能够在实际问题中灵活运用该算法。

一、例题一：743. Network Delay Time

这是一道经典的Dijkstra算法应用题，题目描述如下：有N个网络节点，其中一个节点作为源节点，从该节点出发，每个节点有不同的传输时间，问从源节点出发到其他各节点的最小传输时间是多少，如果无法到达所有节点，则返回-1。

对于这道题，我们可以采用Dijkstra算法来解决。我们需要构建一个图来表示节点之间的传输时间关系，然后利用Dijkstra算法求解最短路径，最终得到源节点到各个节点的最小传输时间。

具体的实现步骤如下：

1. 构建图：根据题目给出的节点和传输时间信息，构建一个图来表示节点之间的传输时间关系。可以使用邻接矩阵或邻接表来表示图的结构。

2. 初始化距离数组：为了记录从源节点到各个节点的最小传输时间，我们需要初始化一个距离数组，用来存储源节点到各个节点的最小传输时间，初始时距离数组中的值全为无穷大。

3. 利用Dijkstra算法进行最短路径求解：从源节点开始，按照Dijkstra算法的思想，逐步更新距离数组中的值，直到得到源节点到各个节点的最小传输时间。

通过以上步骤，我们就可以得到从源节点出发到其他各节点的最小传输时间，从而解决这个网络延迟时间的问题。

二、例题二：1631. Path With Minimum Effort

这是另一道经典的Dijkstra算法应用题，题目描述如下：有一个二维矩阵表示地图，每个格子中包含一个代表路径代价的非负整数，从左上角出发到右下角，每次只能朝上、下、左、右四个方向移动，问怎样移动可以保证路径代价的最小值是多少。