Java实现Floyd算法求最短路径

本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码，供大家参考，具体内容如下

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class TestMainIO {

 /**
  * @param args
  * @throws FileNotFoundException
  */
 public static void main(String[] args) throws FileNotFoundException {
  TestMainIO test_print = new TestMainIO();
  int[][] G = test_print.intputGragh("D:\\Users\\test.txt" , 6);
  int[][] Dis = test_print.floyd(G, 6);
  test_print.printG(Dis, 6);
 }

 public void printG(int[][] G,int n){
  for(int i=0;i<n;i++){
   for(int j=0;j<n;j++){
    System.out.println(i+"->"+j+" "+G[i][j]);
   }
  }
 }

 public int[][] intputGragh(String path , int num) throws FileNotFoundException{
  int[][] G = new int[num][num];
  for(int i=0;i<num;i++){
   for(int j=0;j<num;j++){
    G[i][j]=999;
   }
  }
  Scanner in = new Scanner(new FileInputStream(path));
  while (in.hasNext()) {
   int i = in.nextInt();
   int j = in.nextInt();
   int weight = in.nextInt();
   G[i][j] = weight;
  }
  return G;
 }

 public int[][] floyd(int[][] G,int n){
  int[][] Dis= new int[n][n];
  for(int q=0;q<n;q++){
   for(int w=0;w<n;w++){
    Dis[q][w]=G[q][w];
   }
  }

  for(int k = 0; k < n; k++){
   for(int i=0; i < n; i++ ){
    for(int j=0; j < n; j++){
     if(Dis[i][j]>Dis[i][k]+Dis[k][j]){
      Dis[i][j]=Dis[i][k]+Dis[k][j];
     }
    }
   }
  }
  return Dis;
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：http://blog.csdn.net/limao314/article/details/14451193