从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径
不用覆盖所有的点
Dijkstra算法
Dijkstra算法介绍
• 算法特点:
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
• 算法的思路:
Dijkstra算法采用的是一种贪心的策略，按照路径的长度排序，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
Dijkstra算法示例演示
| 序号 | ------------------- ---------图 --------------------------- | 可选择的路线(所有可以选择的路线) | 最终选择的路线(根据权值的大小) |
|---|---|---|---|
| 第1次执行 |
|
从v0出发有两条路可以选择 1. v0->v1 2. v0->v2 |
按照权值的大小 因为 1>5 选择v0->v1 |
| 第2次执行 |
|
从v1出发有3条路可以选择 1. v1 -> v2 2. v1 -> v4 3. v1 -> v3 |
按照权值的大小 因为 1+3 < 1+5 < 1+7 选择v1->v2 |
| 第3次执行 |
|
从v2出发有2条路可以选择 1. v2 -> v4 2. v2 -> v5 |
按照权值的大小 因为 1+3+1 < 1+3+7 选择v2->v4 |
| 第4次执行 |
|
从v4出发有4条路可以选择 1. v4 ->v3 2. v4->v5 3. v4 -> v6 4. v4 -> v7 |
按照权值的大小 因为 1+3+1 +2 < 1+3+1 +3 < 1+3+1 +6 < 1+3+1 +9 选择v2->v4 |
| 第5次执行 |
|
从v3出发有1条路可以选择 1. v3 ->v6 |
v3 ->v6 |
| 第6次执行 |
|
从v6出发有2条路可以选择 1. v6 -> v7 2. v6 -> v8 |
按照权值的大小 因为 6+2 < 7 选择v6->v7 |
| 第7次执行 |
|
v7 -> v8 |
执行步骤分析
把图用邻接矩阵存储起来
-
首先初始化三个数组
//V0到V0的路路径为0
最短路路径-Dijkstra 算法代码分析 从0开始
(*D)[v0] = 0;
//V0到V0 是没有路路径的.
final[v0] = 1;
//V0到V0是没有路路径的.所以-1;
(*P)[v0] = -1;
final[0] = 1 的意思是v0到v0 已经找到最短路径。不用找了
| 序号 | ----- -------------执行前 --------------------- | --------------------执行后----------------------- | 分析 | 详解 |
|---|---|---|---|---|
| 第1次执行 |
|
|
w = 0, final[0] = 1 条件不满⾜ w = 1, final[1] = 0 ,G.arc[1][1] = 0 ; 1 < 1 条件不满足 w = 2, final[2] = 0 ,G.arc[1][2] = 3 ; 1+3 < D[2]=5 找到V0 -> V2 更短路径. 更新D[2] = 4 ; p[2] = 1; w = 3, final[3] = 0 , G.arc[1][3] = 7 ; 1+7 < D[3]=∞ 找到V0 -> V3 更短路径. 更新D[3] = 1 + 7 = 8; p[3]=1; w = 4, final[4] = 0 , G.arc[1][4] = 5 ; 1+5 < D[4]=∞ 找到V0 -> V4 更更短路路径. 更更新D[4] = 1 + 5 = 6; p[4]= 1; w = 5, final[5] = 0 , G.arc[1][5] = ∞ ; 1+∞ < D[5]=∞ 条件不成立 w = 6, final[6] = 0 , G.arc[1][6] = ∞ ; 1+∞ < D[6]=∞ 条件不成立 w = 7, final[7] = 0 , G.arc[1][7] = ∞ ; 1+∞ < D[7]=∞ 条件不成立 w = 8, final[8] = 0 , G.arc[1][8] = ∞ ; 1+∞ < D[8]=∞ 条件不成立 |
arc[][]是邻接矩阵 当for循环来到2的时候。v1 -> v2 D[原来的v0 -> v1 的最短路径的权值] = min + 当前v2结点的权值arc[1][2] = 3 < D[2] = 5 ; 判断此次路径是V0 -> V1 - > V2否小于 V0 -> V2 如果小于的就更新当前的D数组的值，否则不更新 |
| 第2次执行 |
|
|
w = 0, final[0] = 1 , 条件不满足 w = 1, final[1] = 1 , 条件不满⾜ w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 0,G.arc[2][3] = ∞ ; 4+∞ < D[3]=8;条件不成立 w = 4, final[4] = 0,G.arc[2][4] = 1 ; 4+1 < D[4]=6 找到V0 -> V4 更短路径. 更新D[4] = 4 +1 = 5; p[4]= 2; w = 5, final[5] = 0,G.arc[2][5] = 7 ; 4+7 < D[5]=∞ 找到V0 -> V5 更短路径. 更新D[5] = 4+7 = 11; p[5]= 2; w = 6, final[6] = 0 , G.arc[2][6] = ∞ ; 4+∞ < D[6]=∞ 条件不成立 w = 7, final[7] = 0 , G.arc[2][7] = ∞ ; 4+∞ < D[7]=∞ 条件不成立 w = 8, final[8] = 0 , G.arc[2][8] = ∞ ; 4+∞ < D[8]=∞ 条件不成立 |
|
| 第3次执行 |
|
|
w = 0, final[0] = 1 , 条件不不满⾜足 w = 1, final[1] = 1 , 条件不不满⾜足 w = 2, final[2] = 1 , 条件不不满⾜足 w = 3, final[3] = 0,G.arc[4][3] = 2 ; 5+2 < D[3]=8; 找到V0->V4- >V3更更短路路径, 更更新D[3] = 5+2=7; p[3]=4; w = 4, final[4] = 1,条件不不满⾜足 w = 5, final[5] = 0,G.arc[4][5] = 3 ; 5+3 < D[5]=11 找到V0 -> V5 更短路径. 更更新D[5] = 5+3 = 8; p[5]= 4; w = 6, final[6] = 0 , G.arc[4][6] = 6 ; 5+6 < D[6]=∞ ;找到V0->V6 更短路径, 更新D[6] = 5+6=11,p[6]=4 w = 7, final[7] = 0 , G.arc[4][7] = 9 ; 5+9 < D[7]=∞;找到V0->V7 的更更短路路径,更更新D[7]=5+9=14, p[7]=4 w = 8, final[8] = 0 , G.arc[4][8] = ∞ ; 5+∞ < D[8]=∞ 条件不不成⽴立 |
|
| 第4次执行 |
|
|
w = 0, final[0] = 1 , 条件不满⾜ w = 1, final[1] = 1 , 条件不满⾜ w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 1 , 条件不满足 w = 4, final[4] = 1 , 条件不满⾜ w = 5, final[5] = 0,G.arc[3][5] = ∞ ; 7+∞ < D[5]=8 ; 条件不满⾜ w = 6, final[6] = 0 , G.arc[3][6] = 3 ; 7+3 < D[6]=11 ;找到V0- >V6 更短路径, 更新D[6] = 7+3=10,p[6]=3 w = 7, final[7] = 0 , G.arc[3][7] = ∞ ; 7+∞ < D[7]=14;条件不满足 w = 8, final[8] = 0 , G.arc[3][8] = ∞ ; 7+∞ < D[8]=∞ 条件不成立 |
|
| 第5次执行 |
|
|
w = 0, final[0] = 1 , 条件不满⾜ w = 1, final[1] = 1 , 条件不满足 w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 1 , 条件不满足 w = 4, final[4] = 1 , 条件不满足 w = 5, final[5] = 0,G.arc[5][5] = 0 ; 8+0 < D[5]=8 ; 条件不满足 w = 6, final[6] = 0,G.arc[5][6] = ∞ ; 8+∞ < D[6]=10 ;条件不满足 w = 7, final[7] = 0 , G.arc[5][7] = 5 ; 8+5 < D[7]=14; V1->V7 找 到更更短路径.更新D[7] = 8+5=13, p[7]=5 w = 8, final[8] = 0 , G.arc[5][8] = ∞ ; 8+∞ < D[8]=∞ 条件不成⽴ |
|
| 第6次执行 |
|
|
w = 0, final[0] = 1 , 条件不满⾜ w = 1, final[1] = 1 , 条件不满足 w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 1 , 条件不满足 w = 4, final[4] = 1 , 条件不满足 w = 5, final[5] = 1 , 条件不满足 w = 6, final[6] = 1 , 条件不满⾜ w = 7, final[7] = 0 , G.arc[6][7] = 2 ; 10+2 < D[7]=13; V1->V7 找到更短路径.更新D[7] = 10+2=12, p[7]=6 w = 8, final[8] = 0 , G.arc[6][8] = 7 ; 10+7 < D[8]=∞ ;V1->V8 找 到更短路径,更新D[8] = 10 + 7 = 17, p[8]=6; |
|
| 第7次执行 |
|
|
w = 0, final[0] = 1 , 条件不满足 w = 1, final[1] = 1 , 条件不满足 w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 1 , 条件不满足 w = 4, final[4] = 1 , 条件不满足 w = 5, final[5] = 1 , 条件不满⾜ w = 6, final[6] = 1 , 条件不满⾜ w = 7, final[7] = 1 ,条件不满⾜ w = 8, final[8] = 0 , G.arc[7][8] = 4 ; 12+4 < D[8]=17 ;V1->V8 找到更短路径,更新D[8] = 12+4 = 16, p[8]=7; |
|
| 第8次执行 |
|
|
w = 0, final[0] = 1 , 条件不满⾜ w = 1, final[1] = 1 , 条件不满⾜ w = 2, final[2] = 1 , 条件不满足 w = 3, final[3] = 1 , 条件不满足 w = 4, final[4] = 1 , 条件不满足 w = 5, final[5] = 1 , 条件不满足 w = 6, final[6] = 1 , 条件不满足 w = 7, final[7] = 1 ,条件不满足 w = 8, final[8] = 1 , 条件不满足 |
代码实现
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status;
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];
/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*10.2 求得网图中2点间最短路径
Dijkstra 算法
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
D[v]: 表示从V0到V的最短路径长度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
k = 0;
/*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
int final[MAXVEX];
/*1.初始化数据*/
for(v=0; v<G.numVertexes; v++)
{
//全部顶点初始化为未知最短路径状态0
final[v] = 0;
//将与V0 点有连线的顶点最短路径值;
(*D)[v] = G.arc[v0][v];
//初始化路径数组p = 0;
(*P)[v] = 0;
}
//V0到V0的路径为0
(*D)[v0] = 0;
//V0到V0 是没有路径的.
final[v0] = 1;
//v0到V0是没有路径的
(*P)[v0] = -1;
//2. 开始主循环,每次求得V0到某个顶点的最短路径
for(v=1; v<G.numVertexes; v++)
{
//当前所知距离V0顶点最近的距离
min=INFINITYC;
/*3.寻找离V0最近的顶点*/
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
//w顶点距离V0顶点更近
min = (*D)[w];
}
}
//将目前找到最近的顶点置为1;
final[k] = 1;
/*4.把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
for(w=0; w<G.numVertexes; w++)
{
//如果经过v顶点的路径比现在这条路径长度短,则更新
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
//找到更短路径, 则修改D[W],P[W]
//修改当前路径的长度
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
int main(void)
{
printf("最短路径-Dijkstra算法\n");
int i,j,v0;
MGraph G;
Patharc P;
ShortPathTable D;
v0=0;
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
printf("最短路径路线:\n");
for(i=1;i<G.numVertexes;++i)
{
printf("v%d -> v%d : ",v0,i);
j=i;
while(P[j]!=-1)
{
printf("%d ",P[j]);
j=P[j];
}
printf("\n");
}
printf("\n最短路径权值和\n");
for(i=1;i<G.numVertexes;++i)
printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
printf("\n");
return 0;
}
通过上述代码不难发现 Dijkstra 的时间复杂度是 O(n^2)
个人认为 Dijkstra是最重要的算法之一，这里推荐几道练手题，可以去做
P1938 [USACO09NOV]找工就业Job Hunt
P1457 城堡 The Castle（这是一道 BFS。但是 Dijkstra 可做，且有一定思维难度，也有一些坑，比如如何取出每一面墙和优先顺序之类的细节也很有趣，在这里特别推荐大家做此题）
Floyd算法
•
网友评论