最短路径算法是在图中求两点(或多点)之间的最短路径,我们最常见的最短路径算法有三种:Bellman-ford、Dijkstra、Floyd。
Bellman-ford算法可以用于有负边权的图,如果途图中有负环,算法也可以检验出来,时间复杂度为O(VE)。
Dijkstra算法只能用于边权为正的图中,时间复杂度为O(n^2)。
Floyd可以用于有负权的图中,即使有负环,算法也可以检测出来,可以求任意点的最短路径,有向图和无向图的最小环和最大环。时间复杂度O(n^3)。
Dijkstra算法求单源最短路径问题
大概就是这样一个有权图,Dijkstra算法可以计算任意节点到其他节点的最短路径
算法思路
1.指定一个节点,例如我们要计算 'A' 到其他节点的最短路径
2.引入两个集合(S、U),S集合包含已求出的最短路径的点(以及相应的最短长度),U集合包含未求出最短路径的点(以及A到该点的路径,注意 如上图所示,A->C由于没有直接相连 初始时为∞)
3.初始化两个集合,S集合初始时 只有当前要计算的节点,A->A = 0,U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞,接下来要进行核心两步骤了
4.从U集合中找出路径最短的点,加入S集合,例如 A->D = 2
5.更新U集合路径,if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 则更新U
6.循环执行 4、5 两步骤,直至遍历结束,得到A 到其他节点的最短路径
算法图解
1.选定A节点并初始化,如上述步骤3所示
2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合
3.这时候 A->B, A->C 都为3,没关系。其实这时候他俩都是最短距离,如果从算法逻辑来讲的话,会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ,如图所示这时候A->B距离 其实为 A->D->B
4.思路就是这样,往后就是大同小异了
5.算法结束
参考代码
#define INF 0x7fffffff //定义一个无穷大的值
int mpt[1005][1005]; //用邻结矩阵存储图
int vis[1005];//标记每个点是否加入集合
int dist[1005];//dist[i]表示从起点到i点的最短路
void dijkstra(int s) {//传入起点坐标
for(int i = 1; i <= n; i++)//初始化dist的值
dist[i] = mpt[s][i];
vis[s] = 1;//将起点加入集合
for (int i = 2; i <= n; i++) {//除了起点还剩n-1个点
int minx = INF, v = -1;
for (int j = 1; j <= n; j++) {
if (dist[j] < minx && !vis[j]){
minx = dist[i];//找到最近的点进行更新
v = j;
}
if (v == -1) break;//无法继续更新了,图不连通
vis[v] = 1;//将找到的点加入集合
for (int j = 1; j <= n; j++) {//遍历v的邻接顶点,更新dist
if (!vis[j] && dist[j] > dist[v] + mpt[v][j])//松弛操作
dist[j] = dist[v] + mpt[v][j];//更新
}
}
}
}
Floyd算法求多源最短路径
Floyd-Warshall算法(Floyd-Warshall algorithm),是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
简单的说就是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。
算法的思路
通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入两个矩阵,矩阵D中的元素d[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素p[i][j],表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点。
假设图G中顶点个数为N,则需要对矩阵D和矩阵P进行N次更新。初始时,矩阵D中顶点d[i][j]的距离为顶点i到顶点j的权值;如果i和j不相邻,则d[i][j]=∞,矩阵P的值为顶点p[i][j]的j的值。 接下来开始,对矩阵D进行N次更新。第1次更新时,如果”d[i][j]的距离” > “d[i][0]+d[0][j]”(d[i][0]+d[0][j]表示”i与j之间经过第1个顶点的距离”),则更新d[i][j]为”d[i][0]+d[0][j]”,更新p[i][j]=p[i][0]。 同理,第k次更新时,如果”d[i][j]的距离” > “d[i][k-1]+d[k-1][j]”,则更新d[i][j]为”d[i][k-1]+d[k-1][j]”,p[i][j]=p[i][k-1]。更新N次之后,操作完成!
Floyd算法的实例过程
上面,我们已经介绍了算法的思路,如果,你觉得还是不理解,那么通过一个实际的例子,把算法的过程过一遍,你就明白了,如下图,我们求下图的每个点对之间的最短路径的过程如下:
第一步,我们先初始化两个矩阵,得到下图两个矩阵: D矩阵是“邻接矩阵”
第二步,以v1为中阶,更新两个矩阵:
发现,a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1],所以我们只需要矩阵D和矩阵P,结果如下:
通过矩阵P,我发现v2–v7的最短路径是:v2–v1–v7
第三步:以v2作为中介,来更新我们的两个矩阵,使用同样的原理,扫描整个矩阵,得到如下图的结果:
OK,到这里我们也就应该明白Floyd算法是如何工作的了,他每次都会选择一个中介点,然后,遍历整个矩阵,查找需要更新的值,下面还剩下五步,就不继续演示下去了,理解了方法,我们就可以写代码了。
const int maxn = 105;
int mpt[maxn][maxn]; //用邻结矩阵存储图
void floyd() {
for (int k = 1; k <= n; k++) {//枚举中间点
for (int i = 1; i <= n; i++) {//枚举起点
for (int j = 1; j <= n; j++) {//枚举终点
if (mpt[i][k] + mpt[k][j] < mpt[i][j])//松弛操作
mpt[i][j] = mpt[i][k] + mpt[k][j];
}
}
}
}
课后习题
【2016年真题】使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是()
A.5,2,3,4,6 B.5,2,3,6,4
C.5,2,4,3,6 D.5,2,6,3,4
参考答案:B
【2012年真题】对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是 c,后续得到的其余各最短路径的目标顶点依次是()。
A.d,e,f
B.e,d,f
C.f,d,e
D.f,e,d
参考答案:C
答案解析:考查 Dijkstra 算法最单源最短路径。
从 a 到各顶点的最短路径的求解过程:【排除法】 对于 A,若下一个顶点为 d,路径 a,b,d 的长度 5,而 a,b,c,f 的长度仅为 4,显然错误。
同理可以排除 B。将 f 加入集合 S 后,采用上述的方法也可以排除 D。
【2014年真题】某网络中的路由器运行 OSPF 路由协议,题 42 表是路由器 R1 维护的主要链路状态信息(LSI),题 42 图是根据题 42 表及 R1 的接口名构造出来的网络拓扑。
请回答下列问题。
1)本题中的网络可抽象为数据结构中的哪种逻辑结构?
2)针对题 42 表中的内容,设计合理的链式存储结构,以保存题 42 表中的链路状态信
息(LSI)。要求给出链式存储结构的数据类型定义,并画出对应题 42 表的链式存储结构示意
图(示意图中可仅以 ID 标识结点)。
3)按照迪杰斯特拉(Dijikstra)算法的策略,依次给出 R1 到达题 42 图中子网 192.1.x.x
的最短路径及费用。
参考答案:
考察在给出具体模型时,数据结构的应用。该题很多考生乍看之下以为是网络的题目,
其实题本身并没有涉及太多的网络知识点,只是应用了网络的模型,实际上考察的还是数据
结构的内容。
(1)图
题中给出的是一个简单的网络拓扑图,可以抽象为无向图。
(2)链式存储结构的如下图所示其数据类型定义如下:
typedef struct{ unsigned int ID, IP; }LinkNode; //Link 的结构 typedef struct{ unsigned int Prefix, Mask; }NetNode; //Net 的结构 typedef struct Node{ int Flag; //Flag=1 为 Link;Flag=2 为 Net union{ LinkNode Lnode; NetNode Nnode }LinkORNet; unsigned int Metric; struct Node *next; }ArcNode; //弧结点 typedef struct HNode{ unsigned int RouterID; ArcNode *LN_link; Struct HNode *next; }HNODE; //表头结点
对应题 42 表的链式存储结构示意图如下。
(3)计算结果如下表所示。
【2009年真题】带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
① 设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③ 重复步骤②,直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
参考答案:
该方法不一定能(或不能)求得最短路径。
例如,对于下图所示的带权图,如果按照题中的原则,从 A 到 C 的最短路径是 A->B->C,事实上其最短路径是 A->D->C。
登录后开始许愿
暂无评论,来抢沙发