首页 科技正文

嘉兴市图书馆:最短路径——dijkstra算法代码(c语言)

admin 科技 2020-05-19 14 0

最短路径问题

  看了王道的视频,感受云里雾里的,以是写这个博客来加深明白。(希望能在12点以前写完)

一、总体头脑

dijkstra算法的主要头脑就是基于贪心,找出从v最先的极点到各个点的最短路径,做法入下

1.初始化三个辅助数组

  s[],dist[],path[]

    s[]:这个数组用来符号结点的接见与否,若是该结点被接见,则为1,若是该结点还没有接见,则为0;

    dist[]:这个数组用来纪录当前从v到各个极点的最短路径长度,算法的焦点头脑就是通过不停修改这个表实现;

    path[]:这个数组用来存放最短路径;

2.遍历图,修改上面的各项数组,每次只找最短路径,直到遍历竣事

 

二、代码实现

 

 1 void dijkstra(Graph G, int v)
 2 {
 3     int s[G.vexnum];
 4     int dist[G.vexnum];
 5     int path[G.vexnum];  
 6     for(int i = 0; i < G.vexnum; i++)
 7     {
 8         s[i] = 0;
 9         dist[i] = G.edge[v][i];
10         if(G.edge[v][i] == max || G.edge[v][i] == 0)
11         {
12             path[i] = -1;
13         }
14         else
15         {
16             path[i] = v;
17         }
18         s[v] = 1;
19     }
20     
21     for(int i = 0; i < G.vexnum; i++)
22     {
23         int min  = max;
24         int u;
25         for(int j = 0; j < G.vexnum; j++)
26         {
27             if(s[j] != 1 && dist[j] < min)
28             {
29                 min = dist[j];
30                 u = j;
31             }
32         }
33         s[u] = 1;
34         for(int j = 0; j < G.vexnum; j++)
35         {
36             if(s[j] != 1 && dist[j] > dist[u] + G.edge[u][j])
37             {
38                 dist[j] = dist[u] + G.edge[u][j];
39                 path[j] = u;
40             }
41         }
42     }
43 }

 

 

 

 

三、代码注释

先自己界说一个无穷大的值max

#define max inf

dijkstra算法传入的两个参为

图Graph G;

起点结点 int v;

 

首先我们需要三个辅助数组

1 int s[G.vexnum];//纪录结点时是否被接见过,接见过为1, 没有接见过为0
2     int dist[G.vexnum];//纪录当前的从v结点最先到各个结点的最短路径长度 
3     int path[G.vexnum];//纪录最短路径,存放的是该结点的上一个为最短路径的前驱结点  

初始化三个数组

 1 for(int i = 0; i < G.vexnum; i++)
 2     {
 3         s[i] = 0;//现在每个结点均未被接见过,设为0 
 4         dist[i] = G.edge[v][i];//dist[]数组纪录每个从v结点开到其他i结点边的长度(权值) 
 5         if(G.edge[v][i] == max || G.edge[v][i] == 0)
 6         {
 7             path[i] = -1;
 8         }//若是v到i不存在路径或者i就是v结点时,将path[i]设为-1,意为现在v结点不存在路径到i 
 9         else
10         {
11             path[i] = v;
12         }//反之,若v到i存在路径,则v就是i的前驱结点,将path[i] = v
13         s[v] = 1;//从遍历起点v最先,即已经接见过极点s[v]=1 
14     }

最先遍历数组而且每次修改辅助数组以纪录现在的情形,直至遍历竣事

 1 for(int i = 0; i < G.vexnum; i++)
 2     {
 3         int min  = max;//声明一个min = max用来每次纪录这次遍历找到的最短路径的长度(权值) 
 4         int u;//声明u来纪录这次历找到的最短路径的结点 
 5         for(int j = 0; j < G.vexnum; j++)//最先遍历 找现在的最短路径 
 6         {
 7             if(s[j] != 1 && dist[j] < min)
 8             {
 9                 min = dist[j];
10                 u = j;
11             }//找出v到结点j的最短路径,而且纪录下最短路径的结点u = j 
12         }
13         s[u] = 1;//找到结点u,即已接见过u,s[u] = 1 
14         for(int j = 0; j < G.vexnum; j++)//最先遍历 修改辅助数组的值 
15         {
16             if(s[j] != 1 && dist[j] > dist[u] + G.edge[u][j])
17             {
18                 dist[j] = dist[u] + G.edge[u][j]; 
19                 path[j] = u;
20             }//若是v→j的路径比v →u→j长,那么修改dist[j]的值为 dist[u] + G.edge[u][j],而且修改j的前驱结点为path[j] = u 
21         }
22     }

遍历竣事后,数组dist[]就是存放了起点v最先到各个极点的最短路径长度

最短路径包罗的结点就在path数组中

例如我们获得如下的path[]数组

1 path[0] = -1;//0到自己无前驱结点
2 path[1] = 0;//1的前驱为结点0,0无前驱结点,即最短路径为0 →1
3 path[2] = 1;//2的前驱结为点1,1的前驱结点0,0无前驱结点,即最短路径为0 →1 →2
4 path[3] = 0;//3的前驱为结点0,0无前驱结点,即最短路径为0 →3
5 path[4] = 2;//4的前驱结为点2,2的前驱结为点1,1的前驱结点0,0无前驱结点,即最短路径为0 →1 →2 →4

实在不难看出,每次都市符号已经接见过的节点,接见过的节点不会再更改,即 这样的算法不可逆,也就是dijkstra对于存在负权值的图不适用,明天再更新Floyd算法叭

,

Sunbet

www.ysycy.com与伊顺源清真餐饮达成战略合作,在伊顺及亚太地区建立直营平台。为Sunbet会员提供线上多种娱乐游戏,将用完善的技术、贴心的服务、雄厚的资金赢取每位Sunbet代理、会员的口碑。

版权声明

本文仅代表作者观点,
不代表本站sunbet的立场。
本文系作者授权发表,未经许可,不得转载。

评论