最短路径问题

  昨天自己试了试写一下dijkstra的算法博客

  dijkstra链接在这←

  今天来更floyd算法，感觉非常简单果然暴力才是解决一切的王道

 

一、总体思想

  floyd算法就是每一次从邻接矩阵选取一个顶点k，然后再去矩阵中遍历两个顶点i，j，看看是i→j的路径短，还是i→k→j的路径短，就是完全的暴力，算法和代码非常简单

二、代码实现

 1 void Floyd(Graph G)
 2 {
 3     int arr[G.vexnum][G.vexnum];
 4     for(int i = 0; i < G.vexnum; i++)
 5         for(int j = 0; j < G.vexnum; i++)
 6             arr[i][j] = G.edge[i][j];
 7     
 8     for(int k; k < G.vexnum; k++)
 9         for(int i = 0; i < G.vexnum; i++)
10             for(int j = 0; j < G.vexnum; j++)
11                 if(arr[i][j] > arr[i][k] + arr[k][j])
12                     arr[i][j] = arr[i][k] + arr[k][j];
13  }

三、代码解释

  其实看上面的代码量和代码就知道这个算法很简单  =_=

  传入Floyd算法的参数是Graph G

  首先开辟一个二维数组arr[][]，并且把图的邻接矩阵G.edge[][]赋值给arr[][]，算法的主要思想就是来修改arr[][]值暴力出最短路径

1 int arr[G.vexnum][G.vexnum];//开辟数组arr[][]接收图G.edge[][]的值 
2     for(int i = 0; i < G.vexnum; i++)
3         for(int j = 0; j < G.vexnum; i++)
4             arr[i][j] = G.edge[i][j];//遍历赋值

  然后就是每次选择一个顶点k，再去找两个顶点i，j，对比看看是i→j的路径短，还是i→k→j的路径短

  也就是arr[i][j] 和 arr[i][k] + arr[k][j]两个的值谁的比较小，然后修改arr[][]一直到遍历完毕

1 for(int k; k < G.vexnum; k++)//选取k顶点 
2         for(int i = 0; i < G.vexnum; i++)
3             for(int j = 0; j < G.vexnum; j++)//再选取i，j两个顶点 
4                 if(arr[i][j] > arr[i][k] + arr[k][j])//判断i→j的路径和i→k→j的路径谁比较短 
5                     arr[i][j] = arr[i][k] + arr[k][j];//如果i→k→j的路径更短，则修改数组arr[][]

  写完感觉好短。。不过确实没啥写的，就是O（n3）的暴力，而且这个算法能计算含有负权值的图，dijkstra就不行

  虽然dijkstra的算法只有O（n2），但是它只有一个顶点到剩下顶点的最短路径，如果还是要计算每个点到每个点的最短路径，其实和Floyd一样，也是O（n3）

  最重要的是 ——Floyd算法他好记啊！

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