Floyd-Warshall-最短路徑算法

一.隻有五行的算法--Floyd-Warshall

直接上代碼

此算法是求多源最短路徑

主要思想就是尋找一個中間點，使得兩點通過中間點到達的距離更近

但是這種算法不能處理帶有負權回路的圖

負權回路指的是整個回路的權值為負

因為最短路徑不存在，因為負數沒有最小

參考啊哈算法148頁

package 啊哈;

import java.util.Arrays;

import java.util.Scanner;

public class Floyed_Warshall多源最短路徑 {

    static int[][] e=new int[10][10];

    static int n,m;

    static int inf=99999999;

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner sc=new Scanner(System.in);

        n=sc.nextInt();

        m=sc.nextInt();

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                if(i==j) e[i][j]=0;

                else e[i][j]=inf;//初始化，點與自己距離為0，其他點為無窮大

        for(int i=1;i<=m;i++){

            int a=sc.nextInt();

            int b=sc.nextInt();

            int c=sc.nextInt();

            e[a][b]=c;

        }//有向圖

        //Floyd-Warshall核心算法

        for(int k=1;k<=n;k++)//給出中間點

            for(int i=1;i<=n;i++)//給出出發點

                for(int j=1;j<=n;j++)//給出終點

                    if(e[i][j]>e[i][k]+e[k][j])//判斷出發點通過該中間點到達終點 是否比 原來距離短

                        e[i][j]=e[i][k]+e[k][j];//更新

        for(int i=1;i<=n;i++){

            for(int j=1;j<=n;j++)

                System.out.print(e[i][j]+" ");

            System.out.println();

        }

    }

}