Floyd算法求解最短路径

Floyd算法求解最短路径

• 1、算法概述
• 2、算法实例
• 3、算法实战
• • 3.1 算法描述
  • 3.2 解题思路
  • 3.3 代index.php/tags-41973.html" >���实现

    1、算法概述

      Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。

      核心思路：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

      算法过程：

    • 从任意一条单边路径开始。左右两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

    • 对于每一对顶点u和v，看是否存在一个顶点w使得从u到w再到v比已知的路径更短，如果更短，则更新它。

      上述概念来源于百度百科

      2、算法实例

        如下图所示，我们看怎么来求解两点之间的最短路径。

        如果要让任意两点之间(假设是a到b)的路程变短，智能引入第三个点(假设为k)，并通过这个点k进行中转即a->k->b,才可能缩短为原来从顶点a到顶点b的路程。有时候可能不止一个中转点，而是经过两个或者更多的点进行中转会更短。比如上图中的4号和3号之间的路程本来是a[4][3]=12,如果通过1号中转4->1->3，路程将缩短为e[4][1]+e[1][3]=5+6=11。如果同时通过1号和2号中转的话，从4号到3号的路程会进一步缩短为e[4]+e[1][2]+e[2][3]=5+2+3=10。通过以上分析，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。下面我们模拟该过程。

        我们使用邻接矩阵(二维数组)存储这个图，我们约定自己到自己的路程为0，1号和2号城市的路程为2，则设e[1][2]=2。2号城市无法到达4号城市，设e[2][4]=无穷大我们根据图中的权值得出如下矩阵：

        假设我们现在只允许经过1号顶点中转，求任意两点之间的最短路径。

      //经过1号顶点中转for (int i = 1; i     for (int j = 1; j         if(e[i][j]e[i][1]+e[1][j]){            e[i][j]=e[i][1]+e[1][j];        }    }}    for (int j = 1; j         if(e[i][j]e[i][2]+e[2][j]){            e[i][j]=e[i][1]+e[1][j];        }    }}    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        int N = scan.nextInt();//N个景点        int M = scan.nextInt();//经典之间共M条路        int Q = scan.nextInt();//Q个观景计划        long[][] dist = new long[N + 1][N + 1];        for (int i = 1; i   //初始化为最大值            Arrays.fill(dist[i],Long.MAX_VALUE);            dist[i][i]=0; //对角线赋值0即可(自己到自己)        }        for (int i = 1; i   //初始化两点距离            int u = scan.nextInt();            int v = scan.nextInt();            long w = scan.nextLong();            dist[u][v]=Math.min(dist[u][v],w);            dist[v][u]=Math.min(dist[v][u],w);        }        //Floyd算法        for (int k = 1; k             for (int i = 1; i                 for (int j = 1; j                     if(dist[i][j]dist[i][k]+dist[k][j]){                        dist[i][j]=dist[i][k]+dist[k][j];                    }                }            }        }        //查询        for (int i = 0; i             int start = scan.nextInt();            int end = scan.nextInt();            if(dist[start][end]=Long.MAX_VALUE){                System.out.println(-1);            }else{                System.out.println(dist[start][end]);            }        }    }}