图一
图二
图三
图四
1 import java.util.Scanner; 2 import java.util.LinkedList; 3 public class One { 4 public static void main(String args[]){ 5 int c,r; 6 Scanner scanner=new Scanner(System.in); 7 System.out.println("请输入城市数、路线条数:"); 8 c=scanner.nextInt(); 9 r=scanner.nextInt(); 10 int a[][]=new int[c+1][c+1]; 11 //初始化 12 for(int i=1;i<=c;i++){ 13 for(int j=1;j<=c;j++){ 14 if(i==j)a[i][j]=0; 15 else a[i][j]=999;//999表示无穷大，即i、j没有边 16 } 17 } 18 System.out.println("请输入各条路线:");//读入边 19 for(int k=1;k<=r;k++){ 20 int x=scanner.nextInt(); 21 int y=scanner.nextInt(); 22 int d=scanner.nextInt(); 23 a[x][y]=d; 24 } 25 //Floyd-Warshall核心算法 26 for(int k=1;k<=c;k++){ 27 for(int i=1;i<=c;i++){ 28 for(int j=1;j<=c;j++){ 29 if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j]; 30 } 31 } 32 //输出最终结果 33 for(int i=1;i<=c;i++) 34 for(int j=1;j<=c;j++) 35 if(a[i][j]!=999&&a[i][j]!=0){ 36 System.out.print(a[i][j]+" "); 37 } 38 } 39 } 40 }
结果：
