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; 
 } 
} 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。

声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:notice#nhooo.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。