当前课程知识点：数据结构（Data Structures） > 6. Graph > 6.10 Dijkstra Algorithm > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
前面我们已经介绍了
迪杰斯特拉算法的主要原理
下面我们将为大家讲解一下
这个算法的实现过程
这个算法有三个参数
第一个是指向图的指针G
第二个参数是一个记录最短路径长度的
数组D
第三个参数s表示原点的编号
算法开始的时候
我们需要对数组D来进行初始化
因为一开始我们唯一可以确定的
是从s到s的最短路径长度是等于0
所以在这里我们把D[s]设置为0
而数组中的其它的值
我们把它初始化为无穷大
迪杰斯特拉算法是一个由近及远
探索最短路径长度的过程
每次探索的过程是这样子的
首先选出没有标记的
并且在数组D中具有最小取值的顶点v
在这里v对应的是图中的顶点A
然后给这个顶点打上标记
这个时候我们就可以确定
原点到v的最短路径长度
就是等于数组中的值D[v]
然后接下来我们需要探索
从v出发的那些连边
对每条从v出发的连边
v到w我们都可以得到一条
从原点经过v再到达w的路径
我们知道原点到v的最短路径长度是D[v]
而v到w的连边长度是W[v,w]
所以整条路径的长度在最小的情况下
它是等于D[v]再加上W[v,w]
我们来把这条路径的长度
和数组中所记录的D[v]进行对比
如果这条经过v再到达w的路径
是一条到达W的更短路径
那么我们就可以将数组中的值
来进行更换
替换成为这个更小的路径长度
在这个例子中v就是A顶点
D[v]是等于0的
我们探索从A出发的三条连边
首先A到B的连边长度是等于10
也就是说W[a,b]等于10
所以从原点经过A再到达B的路径长度
它是等于BA加上W[a,b]
它是等于0加上10等于10
而在数组中到达B的路径长度
它记录的是无穷大
所以我们说长度为10的这条路径
是一条更短的到达B的路径
因此我们可以修改数组中
对应位置的值为10
同样道理
在考虑到A到C的连边
以及A到D的连边的时候
都会发现更短的路径
因此在数组中也会做相应的更换
接下来我们需要循环迭代
下面这样一个过程
每执行一次就会确定从原点
到其中一个顶点的最短路径的长度
并且会修改数组中的路径的长度
经过v次迭代之后
我们就可以计算从原点到所有顶点的
最短路径长度
按照上面的过程
接下来我们会确定到达C的最短路径长度
我们给C打上标记
然后我们将探索从C出发的所有连边
并且更新数组中的取值
然后接下来会确定到达B的最段路径长度
并且给B打上标记
然后将探索从B出发的所有连边
并且做相应的数组更新
然后我们会确定到达D的最短路径长度
并且给D打上标记
接着我们探索从D出发的所有连边
并且做相应的数组更新
最后我们会确定到达E的最短路径长度
然后给E打上标记
下面我们来把整个算法的过程实现出来
迪杰斯特拉算法它有三个参数
G是图的指针
D是用来记录最短路径长度的数组
s是原点
我们先要对数组中的值来进行初始化
数组中所有的值一开始都被设置为无穷大
这个无穷大它是一个常量
可以定义为一个非常大的整数
比如最大的INT类型的整数
那么对于原点s
我们设置对应位置的数组的值为0
来去表示从s到s的最短路径长度
是等于0的
然后我们开始一个循环
这个循环执行v次
每次循环的时候
我们将在数组D中选择一个路径长度最短
而且没有访问过的顶点v
这个过程
我们用minVertex这个函数来实现
具体的实现过程我们放到后面去讲
根据前面我们的分析我们知道
v就是所有没有标记的顶点中
距离s最近的顶点
并且s到v的最段路径长度就是D[v]的值
接下来我们就要给v打上一个标记
然后我们将探索从v出发的所有的连边
对v的每个邻居w对应一条连边 v到w
我们将考察一下
从s出发经过v然后再到达w这条路径
我们把这条路径的长度
和数组中所记录的到达w的路径长度
D[w]进行一个对比
如果这条路径它的长度更小
就说明我们找到了一条到达w更短的路径
因此我们相应的要把这条更短的路径长度
用来去替换数组中的D[w]的值
在这个循环执行了v次之后
从原点s出发到图中所有顶点的最段路径
都已经确定下来了
并且把它们的长度记录在数组D中
这个算法就可以成功结束了
现在我们再来重点看一下这里的第6行
minVertex函数的实现
这个minVertex函数返回的是
整数数组D中的具有最小值的
并且是没有访问过的顶点编号
要找到一个整数数组中的最小值
最简单的方法就是
遍历一遍数组中的每一个整数
我们这里面采用的就是
这个简单的遍历方法
首先我们来定义一个整数变量min
用它来记录这个最小值
初始化的时候
我们把min设置为一个非常大的整数
然后我们通过一个for循环
来去取遍所有的顶点编号
如果当前的顶点i是没有标记过的
并且D[i]小于min
我们就要把这个顶点的编号i
记录在变量v中
同时我们去更新min变量
把它更新为D[i]
当这个for循环运行结束的时候
变量v里面所记录的
就是没有标记过的顶点中
具有最小D值的顶点
最后我们就返回v就可以完成这个函数了
目前为止
我们已经完整地实现了迪杰斯特拉算法
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
