图的最短路径拓扑排序和关键路径
- 格式:doc
- 大小:160.00 KB
- 文档页数:30
图论算法四、拓扑排序算法与关键路径,都是在有向无今天讨论的所有算法,今天讨论的所有算法环图中才适用的。
1.拓扑排序AOV(Activity On Vertex Network)顶点活动网络。
所谓AOV网,就是指一个有向无环图。
我们可以把一个AOV网形象地看成是一个大任务的进行流程。
其中的子任务有一定的先后关系,必须完成一个,或某几个子任务后,才能接着完成接下来的任务。
因此,找出子任务的完成顺序就显得很有意义。
显然把每一个任务的前驱任务都放在这个任务之前,就是所有任务的完成顺序。
这样的顺序就叫做“拓扑序列”。
注意,拓扑序列是不唯一的。
构造拓扑序列的拓扑排序算法思想很简单:1)选择一个入度为0的顶点并输出2)然后从AOV网中删除此顶点及以此顶点为起点的所有关联边;3)重复上述两步,直到不存在入度为0的顶点为止。
4)若输出的顶点数小于AOV网中的顶点数,则输出“有回路信息”,否则输出的顶点序列就是一种拓扑序列。
从第四步可以看出,拓扑排序可以用来判断一个有向图是否有环。
只有有向无环图才存在拓扑序列。
算法实现:a)数据结构:indgr[i]:顶点i的入度;stack[]:栈b)初始化:top=0(栈顶指针)c)将初始状态所有入度为0的顶点压栈d)I=0(计数器)e)While栈非空(top>0)doi.顶点v出栈;输出v;计数器增1;ii.For与v邻接的顶点u do1.dec(indgr[u]);2.If indgr[u]=0then顶点u入栈f)EXIT(I=|V|)简单&高效&实用的算法。
上述实现方法复杂度O(V+E)关键路径2.2.关键路径如果我们已经得到了完成任务的顺序,即拓扑序列,接下来我们最关心的问题显然是完成所有的任务最少需要多长时间。
假设工程可以同时进行。
我们开始时可以人为添加2个结点,0和n+1,表示任务开始和任务全部完成。
因为所有的任务都必须完成,根据木桶原理,耗时最长的那条路显然应是完成所有任务的最少耗时。
数据结构——图图的定义和基本术语
定义是由一个顶点集V和一个顶点间的关系集合组成的数据结构
分类
有向图
无向图
基本术语
有(无)向网弧或边带权的图
子图
完全图含有e=n(n-1)/2条边的无向图
有向完全图含有e=n(n-1)条弧的有向图
稀疏图边或弧的个数<nlogn
稠密图边或弧的个数>=nlogn
度(入度+出度)
入度以顶点v为弧尾的弧的数目
出度以顶点v为弧头的弧的数目
路径长度路径上边的数目
连通图图中任意两个顶点之间都有路径相通
图的遍历
深度优先搜索DPS
类似于先序遍历
实质对每个顶点查找其邻接点的过程
广度优先搜索BFS实质通过边或弧找邻接点的过程
图的存储结构
邻接矩阵
有向图:对称统计第i行1的个数可得顶点i的出度
无向图:不对称统计第j列1的个数可得顶点j的入度
邻接表只存储图中已有的弧或边的信息
有向图的十字链表将有向图的邻接表和逆邻接表结合起来的一种链
图的应用
最小生成树
普里姆(Prim)算法
贪心算法
最短路径
Dijkstra算法
Floyd算法
拓扑排序
关键路径。
数据结构的应用的拓扑排序与关键路径算法拓扑排序与关键路径算法是数据结构中重要的应用之一。
拓扑排序通过对有向图的节点进行排序,使得对于任意一条有向边(u,v),节点 u 在排序中都出现在节点 v 之前。
关键路径算法则是用来确定一个项目的关键活动和最短完成时间。
拓扑排序的实现可以通过深度优先搜索或者广度优先搜索来完成。
深度优先搜索是递归地访问节点的所有未访问过的邻居节点,直到没有未访问过的邻居节点为止,然后将该节点添加到拓扑排序的结果中。
广度优先搜索则是通过使用队列来实现的,将节点的邻居节点逐个入队并进行访问,直到队列为空为止。
无论使用哪种方法,拓扑排序都可以通过判断节点的入度来进行。
拓扑排序在很多实际问题中都有广泛应用。
比如在任务调度中,拓扑排序可以用来确定任务间的依赖关系和执行顺序;在编译原理中,拓扑排序可以用来确定程序中变量的定义和使用顺序。
关键路径算法用于确定项目中的关键活动和最短完成时间。
它通过计算每个活动的最早开始时间和最晚开始时间,以及每个活动的最早完成时间和最晚完成时间来实现。
具体步骤如下:1. 构建有向加权图,其中节点表示项目的活动,有向边表示活动间的先后关系,边的权重表示活动的持续时间。
2. 进行拓扑排序,确定活动的执行顺序。
3. 计算每个活动的最早开始时间,即从起始节点到该节点的最长路径。
4. 计算每个活动的最晚开始时间,即从终止节点到该节点的最长路径。
5. 根据每个活动的最早开始时间和最晚开始时间,可以确定关键活动,即最早开始时间与最晚开始时间相等的活动。
6. 计算整个项目的最短完成时间,即从起始节点到终止节点的最长路径。
拓扑排序与关键路径算法在工程管理、任务调度、生产流程优化等领域都有重要应用。
它们能够帮助我们有效地组织和管理复杂的项目,提高工作效率和资源利用率。
在实际应用中,我们可以借助计算机编程以及各种图算法库来实现这些算法,从而更快速、准确地解决实际问题。
综上所述,拓扑排序与关键路径算法是数据结构的重要应用之一。
大连理工大学2024年硕士研究生入学考试大纲科目代码:810 科目名称:数据结构Ⅰ.考查目标计算机学科专业基础综合考试是为大连理工大学招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目,其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力,评价的标准是高等学校计算机科学与技术学科优秀本科生所能达到的及格或及格以上水平,以利于大连理工大学择优选拔,确保硕士研究生的入学质量。
Ⅱ.考查范围计算机学科专业基础综合考试以数据结构专业基础课程。
要求考生系统地掌握数据结构课程的概念、基本原理和基本方法,能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
Ⅲ.考查内容数据结构[考查目标]1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构的基本原理和方法进行问题的分析与求解,具备采用C或C++语言设计与实现算法的能力。
一、线性表1.线性表的定义2.线性表的顺序表示和实现3.线性表的链式表示和实现4.线性表的应用二、栈、队列和数组1.栈和队列的基本概念2.栈的顺序表示和实现3.栈的链式表示和实现4.队列的顺序表示和实现5.队列的链式表示和实现6.栈和队列的应用7.数组的定义,数组的顺序表示和实现8.矩阵的压缩存储三、树与二叉树1.树的定义和基本概念2.二叉树(1) 二叉树的定义及性质(2) 二叉树的存储结构(3) 二叉树的遍历(4) 线索二叉树3.树、森林(1) 树的存储结构(2) 树和二叉树的转换,森林与二叉树的转换(3) 树和森林的遍历4.哈夫曼(Huffman)树和哈夫曼编码四、图1.图的定义和基本概念2.图的存储方式(1) 数组(邻接矩阵)表示法(2) 邻接表3.图的遍历及其应用(1) 深度优先搜索(2) 广度优先搜索4.图的基本应用(1) 最小生成树(2) 最短路径(3) 拓扑排序(4) 关键路径五、查找1.查找的基本概念2.静态查找表(1) 顺序查找法(2) 折半查找法3.动态查找表(1) 二叉排序树和平衡二叉树(2) B-树4.哈希(Hash)表5.查找算法的分析及应用六、排序1.排序的基本概念2.插入排序(1) 直接插入排序(2) 折半插入排序3.起泡排序(bubble sort)4.简单选择排序5.希尔排序(shell sort)6.快速排序7.堆排序8.二路归并排序(merge sort)9.基数排序10.外部排序11.各种排序算法的比较12.排序算法的应用复习参考资料:《数据结构(c语言版)》,严蔚敏,吴伟民编著,清华大学出版社.。
数据结构中的拓扑排序与关键路径问题拓扑排序和关键路径问题是数据结构的重要概念和算法之一。
本文将介绍拓扑排序和关键路径问题的背景、定义、应用以及解决方法。
一、背景在计算机科学中,拓扑排序是一种对有向图的所有顶点进行线性排序的算法。
拓扑排序常常用于确定一个计算或任务的顺序,使得所有的前置任务在后置任务之前完成。
而关键路径则用于确定一个项目计划中所需要的最短时间。
二、拓扑排序的定义与应用拓扑排序的目标是找出一个有向无环图(DAG)中所有顶点的一个线性排序,使得对于任意的有向边 (u, v),顶点 u 在排序中都在顶点 v 的前面。
拓扑排序可以用来检测有向图是否有环,并且找出有向无环图中的一个拓扑序列。
拓扑排序广泛应用于诸如编译器设计、任务调度、依赖关系分析等领域。
例如,在编译器设计中,编译器会先进行语法分析,然后根据语法分析的结果进行语义分析,最后完成代码生成。
这个过程可以看作是一个有向图中各个阶段的前置和后置关系,通过拓扑排序就能确定各个阶段的执行顺序。
三、拓扑排序的解决方法拓扑排序有多种解决方法,其中一种常用的方法是使用深度优先搜索(DFS)算法。
在深度优先搜索中,通过递归地访问每个顶点的邻接顶点,并将已经访问过的顶点加入结果列表。
当所有的邻接顶点都被访问过后,将当前顶点加入结果列表的头部。
最后,得到的结果列表就是一个拓扑序列。
四、关键路径问题的定义与应用关键路径问题是指在一个项目中,确定最长路径所需要的时间,即项目的完成时间。
关键路径决定了整个项目的进度,如果关键路径上的任务延误,将导致整个项目延误。
关键路径问题经常用于项目管理、工程造价核算、资源优化等领域。
例如,在一个建筑项目中,确定各个施工任务的完成时间,将有助于安排人力、物力等资源,从而保证项目能够按时交付。
五、关键路径问题的解决方法关键路径问题可以通过构建活动网络图和关键路径分析来解决。
活动网络图是一个有向无环图(DAG),其中顶点表示各个任务,有向边表示任务之间的先后关系。
高中数学竞赛图论
高中数学竞赛图论是一门涉及图论的数学竞赛,它是一种比较复杂的数学竞赛,要求参赛者具备较强的数学基础和较强的抽象思维能力。
高中数学竞赛图论的内容主要包括图的定义、图的性质、图的表示、图的构造、图的搜索、图的排序、图的最短路径等。
图的定义是指图的基本概念,它是一种由节点和边组成的数据结构,节点表示图中的实体,边表示实体之间的关系。
图的性质是指图的基本特征,它可以分为有向图和无向图,有向图中的边有方向,无向图中的边没有方向。
图的表示是指图的表示方法,它可以用邻接矩阵、邻接表和边表等方法来表示。
图的构造是指图的构造方法,它可以用深度优先搜索和广度优先搜索等方法来构造。
图的搜索是指在图中搜索某个节点或路径的方法,它可以用深度优先搜索和广度优先搜索等方法来搜索。
图的排序是指将图中的节点按照某种顺序排列的方法,它可以用拓扑排序和关键路径法等方法来排序。
图的最短路径是指在图中搜索两个节点之间的最短路径的方法,它可以用迪杰斯特拉算法和弗洛伊德算法等方法来求解。
高中数学竞赛图论是一门涉及图论的数学竞赛,它要求参赛者具备较强的数学基础和较强的抽象思维能力,参赛者需要掌握图的定义、图的性质、图的表示、图的构造、图的搜索、图的排序、图的最短路径等知识,并能够熟练运用这些知识来解决实际问题。
只有具备较强的数学基础和较强的抽象思维能力,才能在高中数学竞赛图论中取得优异的成绩。
详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景:假设要在n个城市之间建立通信联络网,则连通n个城市只需要n—1条线路。
这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价。
n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢?1.2 分析问题(建立模型):可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示:G5G5的三棵生成树:可以证明,对于有n 个顶点的无向连通图,无论其生成树的形态如何,所有生成树中都有且仅有n-1 条边。
1.3最小生成树的定义:如果无向连通图是一个网,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树,简称为最小生成树。
最小生成树的性质:假设N=(V,{ E}) 是个连通网,U是顶点集合V的一个非空子集,若(u,v)是个一条具有最小权值(代价)的边,其中,则必存在一棵包含边(u,v)的最小生成树。
1.4 解决方案:两种常用的构造最小生成树的算法:普里姆(Prim)和克鲁斯卡尔(Kruskal)。
他们都利用了最小生成树的性质1.普里姆(Prim)算法:有线到点,适合边稠密。
时间复杂度O(N^2)假设G=(V,E)为连通图,其中V 为网图中所有顶点的集合,E 为网图中所有带权边的集合。
2020年计算机408数据结构算法题一、引言数据结构与算法是计算机科学和计算机工程领域中的核心内容,也是计算机科班学生必修的一门重要课程。
每年的计算机408考试中,数据结构与算法题型都是考生们备考的重点和难点之一。
了解并掌握2020年计算机408数据结构算法题的内容和出题特点,对于考生们备考复习具有重要的指导意义。
二、2020年计算机408数据结构算法题概述2020年计算机408数据结构算法题涵盖了以下主要内容:1. 线性表2. 树和二叉树3. 图4. 排序算法5. 查找算法接下来将分别对以上内容进行详细介绍和分析,并针对每个部分的题型特点进行总结和归纳。
三、线性表线性表是数据结构中最基本的一种结构,包括顺序表和链表两种类型。
在2020年计算机408数据结构算法题中,与线性表相关的题型主要包括如下内容:1. 顺序表的基本操作2. 链表的插入和删除3. 线性表的应用实例以上内容中,顺序表的基本操作涉及数组的使用和基本的插入、删除等操作,而链表的插入和删除则需要考生掌握指针的运用和链表结构的特点。
在解答线性表的应用实例时,考生需要具备一定的抽象思维能力,能够将具体问题抽象为线性表的操作流程,并给出相应的算法实现。
四、树和二叉树树和二叉树是数据结构中的重要内容,在2020年计算机408数据结构算法题中所涉及的内容主要包括:1. 二叉树的遍历2. 二叉树的建立和操作3. 树的遍历和操作4. 树和二叉树的应用实例在解答二叉树的遍历题目时,考生需要熟练掌握前序、中序和后序三种遍历方式的递归和非递归实现方法,并能够灵活应用。
对于二叉树的建立和操作题目,需要考生具备一定的递归思维能力和对指针操作的熟练运用。
树和二叉树的应用实例则需要考生在理解问题的基础上,通过树和二叉树的操作来解决具体问题,涉及到对树结构的应用和实际意义的理解。
五、图图是数据结构中的另外一种重要结构,而在2020年计算机408数据结构算法题中涵盖的图的内容主要包括:1. 图的存储结构2. 图的遍历和搜索算法3. 最短路径算法4. 拓扑排序和关键路径算法5. 最小生成树算法在解答图的存储结构题目时,考生需要了解邻接矩阵和邻接表两种存储结构的特点和区别,并能够根据具体问题选择合适的存储结构。
拓扑排序与关键路径分析拓扑排序和关键路径分析是项目管理和图论中常用的两种技术,用于分析和优化活动的执行顺序。
在本文中,我们将探讨这两种技术的原理、应用和实施方法。
一、拓扑排序拓扑排序是一种用于有向无环图(DAG)的节点排序方法,使得图中的每条边的起始节点都排在终止节点的前面。
在拓扑排序中,节点表示活动,边表示活动间的先后关系。
拓扑排序的实现可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来完成。
DFS方式会将所有可能的路径都遍历一遍,直到没有后续节点为止。
而BFS方式通过从源节点开始,按广度优先的顺序依次处理各个节点,直到所有节点处理完毕。
拓扑排序在项目管理中被广泛应用,用于确定活动执行的先后顺序,确保项目按计划有序地进行。
通过拓扑排序,可以发现项目中的关键路径,进而对项目进行合理的资源分配和时间安排。
二、关键路径分析关键路径分析是项目管理中用于确定项目完成所需的最短时间的方法。
关键路径是指项目中的一条从起始节点到结束节点的路径,其上的活动紧密相连且没有松弛时间,任何活动的延误都会导致整个项目的延误。
关键路径分析需要确定每个活动的最早开始时间、最晚开始时间、最早完成时间和最晚完成时间。
通过计算差异,可以找到关键路径上的活动和总体项目的最短完成时间。
关键路径分析在项目管理中对决策和资源管理具有重要意义。
通过确定关键路径,项目经理可以对重要活动进行优化和调整,以确保项目按时完成。
此外,关键路径还可以用于资源的分配和调度,以提高项目的效率和质量。
三、拓扑排序与关键路径分析的实施方法要实施拓扑排序和关键路径分析,需要按照以下步骤进行:1. 确定项目的活动和其间的依赖关系。
将活动表示为节点,依赖关系表示为边。
2. 使用拓扑排序算法,对活动进行排序,得到一个合理的活动执行顺序。
3. 计算每个活动的最早开始时间、最晚开始时间、最早完成时间和最晚完成时间。
4. 根据计算结果,找到关键路径上的活动,确定项目的最短完成时间。
数据结构课程辅导---图的最短路径、拓扑排序和关键路径一、最短路径由图的概念可知,在一个图中,若从一顶点到另一顶点存在着一条路径(这里只讨论无回路的简单路径),则称该路径长度为该路径上所经过的边的数目,它也等于该路径上的顶点数减1。
由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同,即路径长度不同,我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径,其路径长度叫做最短路径长度或最短距离。
上面所述的图的最短路径问题只是对无权图而言的,若图是带权图,则把从一个顶点i到图中其余任一个顶点j的一条路径上所经过边的权值之和定义为该路径的带权路径长度,从v i到v j可能不止一条路径,我们把带权路径长度最短(即其值最小)的那条路径也称作最短路径,其权值也称作最短路径长度或最短距离。
例如,在图3-1中,从v0到v4共有三条路径:{0,4},{0,1,3,4}和{0,1,2,4},其带权路径长度分别为30,23和38,可知最短路径为{0,1,3,4},最短距离为23。
图3-1 带权图和对应的邻接矩阵实际上,这两类最短路径问题可合并为一类,这只要把无权图上的每条边标上数值为1的权就归属于有权图了,所以在以后的讨论中,若不特别指明,均认为是求带权图的最短路径问题。
求图的最短路径问题用途很广。
例如,若用一个图表示城市之间的运输网,图的顶点代表城市,图上的边表示两端点对应城市之间存在着运输线,边上的权表示该运输线上的运输时间或单位重量的运费,考虑到两城市间的海拔高度不同,流水方向不同等因素,将造成来回运输时间或运费的不同,所以这种图通常是一个有向图。
如何能够使从一城市到另一城市的运输时间最短或者运费最省呢?这就是一个求两城市间的最短路径问题。
求图的最短路径问题包括两个方面:一是求图中一顶点到其余各顶点的最短路径,二是求图中每对顶点之间的最短路径。
下面分别进行讨论。
1. 从一顶点到其余各顶点的最短路径对于一个具有n个顶点和e条边的图G,从某一顶点v i(称此为源点)到其余任一顶点v j(称此为终点)的最短路径,可能是它们之间的边(i,j)或<i,j>,也可能是经过k个(1≤k≤n-2,最多经过除源点和终点之外的所有顶点)中间顶点和k+1条边所形成的路径。
例如在图3-1中,从v0到v1的最短路径就是它们之间的有向边<0,1>,其长度为3;从v0到v4的最短路径经过两个中间点v1和v3以及三条有向边<0,1>,<1,3>和<3,4>,其长度为23。
那么,如何求出从源点i到图中其余每一个顶点的最短路径呢?狄克斯特拉(Dijkstra)于1959年提出了解决此问题的一般算法,具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度,每次求出从源点i到一个终点m的最短路径及长度后,都要以该顶点m作为新考虑的中间点,用v i到v m的最短路径和最短路径长度对v i到其它尚未求出最短路径的那些终点的当前最短路径及长度作必要地修改,使之成为当前新的最短路径和最短路径长度,当进行n-2次(因最多考虑n-2个中间点)后算法结束。
狄克斯特拉算法需要设置一个集合,假定用S表示,其作用是保存已求得最短路径的终点序号,它的初值中只有一个元素,即源点i,以后每求出一个从源点i到终点m的最短路径,就将该顶点m并入S集合中,以便作为新考虑的中间点;还需要设置一个整型(假定权值类型为整型)数组dist[MaxVertexNum],该数组中的第j个元素dist[j]用来保存从源点i到终点j的目前最短路径长度,它的初值为(i,j)或<i,j>边上的权值,若v i到v j没有边,则权值为MaxValue,以后每考虑一个新的中间点时,dist[j]的值可能变小;另外,再设置一个与dist数组相对应的、类型为adjlist的邻接表表头向量数组path,该数组中的第j个元素path[j]指向一个单链表,该单链表中保存着从源点i到终点j的目前最短路径,即一个顶点序列,当v i到v j存在着一条边时,则path[j]初始指向由顶点i和j构成的单链表,否则path[j]的初值为空。
此算法的执行过程是:首先从S集合以外的顶点(即待求出最短路径的终点)所对应的dist数组元素中,查找出其值最小的元素,假定为dist[m],该元素值就是从源点i到终点m的最短路径长度(证明从略),对应path数组中的元素path[m]所指向的单链表链接着从源点i到终点m 的最短路径,即经过的顶点序列或称边序列;接着把已求得最短路径的终点m并入集合S中;然后以v m作为新考虑的中间点,对S集合以外的每个顶点j,比较dist[m]+GA[m][j](GA为图G的邻接矩阵)与dist[j]的大小,若前者小于后者,表明加入了新的中间点v m之后,从v i到v j的路径长度比原来变短,应用它替换dist[j]的原值,使dist[j]始终保持到目前为止最短的路径长度,同时把path[m]单链表复制到path[j]上,并在其后插入v j结点,使之构成从源点i到终点j的目前最短路径。
重复n-2次上述运算过程,即可在dist数组中得到从源点i到其余每个顶点的最短路径长度,在path数组中得到相应的最短路径。
为了简便起见,可采用一维数组s[n]来保存已求得最短路径的终点的集合S,具体做法是:若顶点j在集合S中,则令数组元素s[j]的值取1,否则取0。
这样,当判断一个顶点j是否在集合S以外时,只要判断对应的数组元素s[j]是否为0即可。
例如,对于图3-1来说,若求从源点v0到其余各顶点的最短路径,则开始时三个一维数组s,dist和path的值为:s dist path下面开始进行第一次运算,求出从源点v 0到第一个终点的最短路径。
首先从s 元素为0的对应dist 元素中,查找出值最小的元素,求得dist[2]的值最小,所以第一个终点为v 1, 最短距离为dist[2]=3,最短路径为path[2]={0,1},接着把s[1]置为1,表示v 1已加入S 集合中,然后以v 1为新考虑的中间点,对s 数组中元素为0的每个顶点j (此时2≤j ≤4)的目前最短路径长度dist[j]和目前最短路径path[j]进行必要地修改,因dist[1]+GA[1][2]=3+25=28,小于dist[2]=∞,所以将28赋给dist[2],将path[1]并上v 2后赋给path[2],同理因dist[1]+GA[1][3]=3+8=11,小于dist[3]=∞,所以将11赋给dist[3],将path[1]并上v 3后赋给path[3],最后再看从v 0到v 4,以v 1作为新考虑的中间点的情况,由于v 1到v 4没有出边,所以GA[1][4]=∞,故dist[1]+GA[1][4]不小于dist[4],因此dist[4]和path[4]无需修改,应维持原值。
至此,第一次运算结束,三个一维数组的当前状态为:0 1 2 3 4 s dist path下面开始进行第二次运算,求出从源点v 0到第二个终点的最短路径。
首先从s 数组中元素为0的对应dist 元素中,查找出值最小的元素,求得dist[3]的值最小,所以第二个终点为v 3, 最短距离为dist[3]=11,最短路径为path[3]={0,1,3},接着把s[3]置为1,然后以v 3作为新考虑的中间点,对s 中元素为0的每个顶点j (此时j=3,5)的dist[j]和path[j]进行必要的修改,因dist[3]+GA[3][2]=11+4=15,小于dist[2]=28,所以将15赋给dist[2],将path[3]并上v 2后赋给path[2],同理,因dist[3]+GA[3][4]=11+12=23,小于dist[4]=30,所以将23赋给dist[4],将path[3]并上v4后赋给path[4]。
至此,第二次运算结束,三个一维数组的当前状态为:0 1 2 3 4s Array distpath下面开始进行第三次运算,求出从源点v0到第三个终点的最短路径。
首先从s中元素为0的对应dist元素中,查找出值最小的元素为dist[2],所以求得第三个终点为v2,最短距离为dist[2]=15,最短路径为path[2]={0,1,3,2},接着把s[2]置为1,然后以v2作为新考虑的中间点,对s中元素为0的每个顶点j(此时只有v4一个)的dist[j]和path[j]进行必要的修改,因dist[2]+GA[2][4]=15+10=25,大于dist[4]=23,所以无需修改,原值不变。
至此,第三次运算结束,三个一维数组的当前状态为:sdistpath由于图中有5个顶点,只需运算3次,即n-2次,虽然此时还有一个顶点未加入S集合中,但它的最短路径及最短距离已经最后确定,所以整个运算结束。
最后在dist中得到从源v0到每个顶点的最短路径长度,在path中得到相应的最短路径。
如果用图形表示上述过程中每次运算的结果,则对应的图形分别如图3-2(b)~(e)所示,其中实线有向边所指向的顶点为集合S中的顶点,虚线有向边所指向的顶点为集合S外的顶点;S集合中的顶点上所标数值为从源点v0到该顶点的最短路径长度,从源点v0到该顶点所经过的有向边为从v0到该顶点的最短路径;S集合外的顶点上所标数值为从源点v0到该顶点的目前最短路径长度,从v0到该顶点所经过的有向边为从v0到该顶点的目前最短路径。
为了便于对照分析,把图3-1(a)重画于图3-2(a)中。
图3-2 利用狄克斯特拉算法求最短路径的图形说明根据以上分析和举例,不难给出狄克斯特拉算法的描述:void Dijkstra(adjmatrix GA, int dist[],adjlist path, int i, int n)//利用狄克斯特拉算法求图GA中从顶点i到其余每个顶点间的//最短距离和最短路径,它们分别被存于数组dist和path数组中{int j,k,w,m;//定义作为集合使用的动态数组sint* s=new int[n];//分别给s,dist和path数组赋初值for(j=0; j<n; j++) {if(j==i)s[j]=1;elses[j]=0;dist[j]=GA[i][j];if(dist[j]<MaxValue && j!=i) {edgenode* p1=new edgenode;edgenode* p2=new edgenode;p1->adjvex=i;p2->adjvex=j;p2->next=NULL;p1->next=p2;path[j]=p1;}elsepath[j]=NULL;}//共进行n-2次循环,每次求出从源点i到终点m的最短路径及长度 for(k=1; k<=n-2; k++){//求出第k个终点mw=MaxValue; m=i;for(j=0; j<n; j++)if(s[j]==0 && dist[j]<w) {w=dist[j];m=j;}//若条件成立,则把顶点m并入集合S中,否则退出循环,因为剩余 //的顶点,其最短路径长度均为MaxValue,无需再计算下去 if(m!=i)s[m]=1;elsebreak;//对s元素为0的对应dist和path中的元素作必要修改 for(j=0; j<n; j++)if(s[j]==0 && dist[m]+GA[m][j]<dist[j]) {dist[j]=dist[m]+GA[m][j];PATH(path, m, j); //调用此函数,由到顶点m的//最短路径和顶点j构成到顶点j的目前最短路径 }}}PATH函数的定义如下:void PATH(adjlist path, int m, int j)//由到顶点m的最短路径和顶点j构成到顶点j的目前最短路径 {edgenode *p, *q, *s;//把顶点j的当前最短路径清除掉p=path[j];while(p!=NULL) {path[j]=p->next;delete p;p=path[j];}//把到顶点m的最短路径拷贝过来到顶点j的最短路径上 p=path[m];while(p!=NULL) {q=new edgenode;q->adjvex=p->adjvex;if(path[j]==NULL)path[j]=q;elses->next=q;s=q;p=p->next;}//把顶点j加入到path[j]单链表的最后,形成新的目前最短路径 q=new edgenode;q->adjvex=j;q->next=NULL;s->next=q;}2. 每对顶点之间的最短路径求图中每对顶点之间的最短路径是指把图中任意两个顶点v i和v j(i ≠j)之间的最短路径都计算出来。