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算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为①，逐步搜索，每次找出一个结点到源点①的最短路径，直至完成所有结点的计算。

定定定定定定dist[N]定vo,vi,G[N][N]定定定定定s[N],i,j,prev[N]K=0K

false;dist[v] =

cost[v0][v];Yfinal[v0] = trueNi=0i

dist[w] < minMin = dist[w]v = w;YYYW++定定定定final[v] = trueW=0W

dist[v] +

cost[v][w] <

dist[w]dist[w] =

dist[v] +

cost[v][w];YW++Ni=0i

Dijkstra算法的流程图

需求和规格说明：

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。实现注释：

想要实现的功能：

Dijkstra算法是用来求任意两个顶点之间的最短路径。在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径。

已经实现的功能：

在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个全局变量的二维数组，用它来存储任意两个顶点之间的边的权值。然后通过最短路径的计算，输入从任意两个顶点之间的最短路径的大小。

用户手册：

对于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的任意两个顶点之间的边的权值的二维数组的初始化，即将要通过Dijkstra算法求最短路径的图各条边的权值放入二维数组中。这样程序就可以自动的计算出任意两个顶点之间的最短路径并且进行输出。

Dijkstra算法

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

如果用本算法求一个图中全部的最短路，则要以每个点为源调用一次Dijkstra算法。

适用条件与限制

有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。

用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)

算法流程

在以下说明中，s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]

1.

初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。

2.

循环n-1次：

1. 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。

2. 对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]

3. 结束。此时对于任意的u，dist[u]就是s到u的距离。

{单源最短路径的Dijkstra算法。使用二叉堆挑选总复杂度O((e+v)logv)}

const

maxn=100;

type

link=^node; //邻接表类型

node=record

v,w :integer;

next :link;

end;

htype=record //堆节点

v,d,p :integer;

end;

var