有向网络(带权的有向图)的最短路径Dijkstra算法
什么是最短路径?
单源最短路径(所谓单源最短路径就是只指定一个顶点,最短路径是指其他顶点和这个顶点之间的路径的权值的最小值)
什么是最短路径问题?
给定一带权图,图中每条边的权值是非负的,代表着两顶点之间的距离。指定图中的一顶点为源点,找出源点到其它顶点的最短路径和其长度的问题,即是单源最短路径问题。
什么是Dijkstra算法?
求解单源最短路径问题的常用方法是Dijkstra(迪杰斯特拉)算法。该算法使用的是贪心策略:每次都找出剩余顶点中与源点距离最近的一个顶点。
算法思想
带权图G=<V,E>,令S为已确定了最短路径顶点的集合,则可用V-S表示剩余未确定最短路径顶点的集合。假设V0是源点,则初始 S={V0}。用数组Distance表示源点V0到其余顶点的路径长度,用数组pre[i]表示最短路径序列上顶点i的前一个顶点。初始时,pre[i]都是源点的下标。接下来需重复两个步骤:
- 从当前Distance[i]找出最小的一个,记录其下标v=i,源点V0到顶点Vv的最短路径即已确定,把Vv加入S。
- 更新源点到剩余顶点的最短路径长度。更新方法是:以上一步的顶点Vv为中间点,若Distance[v]+weight(v,i)<Distance[i],则修改值:pre[i]=v;Distance[i]=Distance[v]+weight(v,i);
重复以上两个步骤,直至所有顶点的最短路径都已找到。
需要指出,Dijkstra算法求解的不仅是有向图,无向图也是可以的。下面给出一个完整的有向带权图的实例:
下面举例:
有向带权图
Dijkstra算法的求解过程(规定INF是infinity无穷大的意思。)
基于邻接矩阵存储的有向网络的Dijkstra算法的简单实现:
const int infinity = ; //定义无穷常量,用1000表示 //定义图结构,采用邻接矩阵存储形式 template <int max_size> class Graph { private: /*邻接矩阵,对于有向网络(带权的有向图)其中存放的是权值*/ adjacent[max_size][max_size]; public: void Dijkstra(int); //Dijkstra算法,求最短路径 }; //Dijkstra算法实现(基于邻接矩阵存储的带权有向图) void Graph::Dijkstra(int vertex) { //注意:下标表示结点 int count = ; //用于记录访问过的结点数目,后面用于控制循环 bool find[max_size]; //用于标记已经找到最短路径的结点 int pre[max_size]; //用于存放当前结点的前驱结点的最短路径 int distance[max_size]; //用于存放当前结点的最短路径 //初始化 for(int i=;i<max_size;i++) pre[i] = vertex; //开始所有结点的前驱结点都是开始的vertex for(int i=;i<max_size;i++) distance[i] = adjacent[vertex][i]; //邻接矩阵中存放的权值就是距离 for(int i=;i<max_size;i++) find[i] = false; //初始化所有结点都没有找到最短路径 find[vertex] = true; int v = vertex; //用来迭代顶点的变量 int d; //用来表示距离 while(count < max_size) { d = infinity; for(int i=;i<max_size;i++) //找到离最初结点最短路径的一个未访问到的结点 { if(!find[i] && distance[i]<d) { d = diatance[i]; v = i; } } find[v] = true; //更新剩余的结点的前驱和最短距离 for(int i=;i<max_size;i++) { if(!find[i]) { /*将上面找到的最短路径的结点作为起始点, *连到其他未访问过的结点上, *当比从最初结点到这个结点的路径短的时候, *就将上个结点作为前驱结点,更新一下即可*/ d = distance[v] + adjacent[v][i]; if(d < distance[i]) { pre[i] = v; distance[i] = d; } } } count++; } }
参考:http://blog.csdn.net/zhangxiangdavaid/article/details/38360337
相关推荐
燕哥带你学算法 2020-05-31
chenfei0 2020-02-09
风吹夏天 2019-12-07
Happyunlimited 2019-11-12
humothetrader 2019-06-21
duyifei0 2019-06-21
duyifei0 2019-06-21
zonglinzonglin 2018-08-02
MyronCham 2019-04-26
韦一笑 2011-05-17
lhtzbj 2017-12-12
slxshare 2019-01-17
Masimaro 2020-06-14
rein0 2020-05-03
风吹夏天 2020-05-03
lixiaotao 2020-04-26
horizonheart 2020-04-18
RememberMePlease 2020-04-18
ustbfym 2020-03-03