最短路径问题

  看了王道的视频，感觉云里雾里的，所以写这个博客来加深理解。（希望能在12点以前写完）

 （floyd算法链接在底部，也可以直接点击这个超连接）

一、总体思想

 

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算法叭

版权声明：本文为luoyoucode原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/luoyoucode/p/12913624.html