最短路径问题

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

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

一、总体思想

dijkstra算法的主要思想就是基于贪心，找出从v开始的顶点到各个点的最短路径，做法入下

1.初始化三个辅助数组

s[],dist[],path[]

s[]:这个数组用来标记结点的访问与否，如果该结点被访问，则为1，如果该结点还没有访问，则为0；

dist[]:这个数组用来记录当前从v到各个顶点的最短路径长度，算法的核心思想就是通过不断修改这个表实现；

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

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

二、代码实现

 void dijkstra(Graph G, int v)

 {

     int s[G.vexnum];

     int dist[G.vexnum];

     int path[G.vexnum];

     for(int i = ; i < G.vexnum; i++)

     {

         s[i] = ;

         dist[i] = G.edge[v][i];

         if(G.edge[v][i] == max || G.edge[v][i] == )

         {

             path[i] = -;

         }

         else

         {

             path[i] = v;

         }

         s[v] = ;

     }

     for(int i = ; i < G.vexnum; i++)

     {

         int min  = max;

         int u;

         for(int j = ; j < G.vexnum; j++)

         {

             if(s[j] !=  && dist[j] < min)

             {

                 min = dist[j];

                 u = j;

             }

         }

         s[u] = ;

         for(int j = ; j < G.vexnum; j++)

         {

             if(s[j] !=  && dist[j] > dist[u] + G.edge[u][j])

             {

                 dist[j] = dist[u] + G.edge[u][j];

                 path[j] = u;

             }

         }

     }

 }

三、代码解释

先自己定义一个无穷大的值max

#define max inf

dijkstra算法传入的两个参为

图Graph G；

起点结点 int v；

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

 int s[G.vexnum];//记录结点时是否被访问过，访问过为1， 没有访问过为0

     int dist[G.vexnum];//记录当前的从v结点开始到各个结点的最短路径长度

     int path[G.vexnum];//记录最短路径，存放的是该结点的上一个为最短路径的前驱结点

初始化三个数组

 for(int i = ; i < G.vexnum; i++)

     {

         s[i] = ;//目前每个结点均未被访问过，设为0

         dist[i] = G.edge[v][i];//dist[]数组记录每个从v结点开到其他i结点边的长度（权值）

         if(G.edge[v][i] == max || G.edge[v][i] == )

         {

             path[i] = -;

         }//如果v到i不存在路径或者i就是v结点时，将path[i]设为-1，意为目前v结点不存在路径到i

         else

         {

             path[i] = v;

         }//反之，若v到i存在路径，则v就是i的前驱结点，将path[i] = v

         s[v] = ;//从遍历起点v开始，即已经访问过顶点s[v]=1

     }

开始遍历数组并且每次修改辅助数组以记录目前的情况，直至遍历结束

 for(int i = ; i < G.vexnum; i++)

     {

         int min  = max;//声明一个min = max用来每次记录这次遍历找到的最短路径的长度（权值）

         int u;//声明u来记录这次历找到的最短路径的结点

         for(int j = ; j < G.vexnum; j++)//开始遍历 找目前的最短路径

         {

             if(s[j] !=  && dist[j] < min)

             {

                 min = dist[j];

                 u = j;

             }//找出v到结点j的最短路径，并且记录下最短路径的结点u = j

         }

         s[u] = ;//找到结点u，即已访问过u，s[u] = 1

         for(int j = ; j < G.vexnum; j++)//开始遍历 修改辅助数组的值

         {

             if(s[j] !=  && dist[j] > dist[u] + G.edge[u][j])

             {

                 dist[j] = dist[u] + G.edge[u][j]；

                 path[j] = u;

             }//如果v→j的路径比v →u→j长，那么修改dist[j]的值为 dist[u] + G.edge[u][j]，并且修改j的前驱结点为path[j] = u

         }

     }

遍历结束后，数组dist[]就是存放了起点v开始到各个顶点的最短路径长度

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

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

 path[] = -;//0到自己无前驱结点

 path[] = ;//1的前驱为结点0,0无前驱结点，即最短路径为0 →1

 path[] = ;//2的前驱结为点1,1的前驱结点0，0无前驱结点，即最短路径为0 →1 →2

 path[] = ;//3的前驱为结点0,0无前驱结点，即最短路径为0 →3

 path[] = ;//4的前驱结为点2,2的前驱结为点1,1的前驱结点0，0无前驱结点，即最短路径为0 →1 →2 →4

其实不难看出，每次都会标记已经访问过的节点，访问过的节点不会再更改，即这样的算法不可逆，也就是dijkstra对于存在负权值的图不适用，明天再更新Floyd算法叭

巴特西

最短路径——dijkstra算法代码（c语言）

最短路径问题

一、总体思想

二、代码实现

三、代码解释

最新文章

热门文章