Java实现Floyd算法求最短路径

时间:2021-10-28 07:47:14

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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