Java實現Floyd算法的示例代碼
一 問題描述
求節點0到節點2的最短路徑。
二 代碼
package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 頂點數最大值 static final int INF = 0x3f3f3f3f; //無窮大 static final int dist[][] = new int[MaxVnum][MaxVnum]; // 最短距離 static final int p[][] = new int[MaxVnum][MaxVnum]; // 前驅數組 static final boolean flag[] = new boolean[MaxVnum]; // 如果 s[i] 等於 true,說明頂點 i 已經加入到集合 S ;否則頂點 i 屬於集合 V-S static int locatevex(AMGraph G, char x) { for (int i = 0; i < G.vexnum; i++) // 查找頂點信息的下標 if (x == G.Vex[i]) return i; return -1; // 沒找到 } static void CreateAMGraph(AMGraph G) { Scanner scanner = new Scanner(System.in); int i, j; char u, v; int w; System.out.println("請輸入頂點數:"); G.vexnum = scanner.nextInt(); System.out.println("請輸入邊數:"); G.edgenum = scanner.nextInt(); System.out.println("請輸入頂點信息:"); // 輸入頂點信息,存入頂點信息數組 for (int k = 0; k < G.vexnum; k++) { G.Vex[k] = scanner.next().charAt(0); } //初始化鄰接矩陣所有值為0,如果是網,則初始化鄰接矩陣為無窮大 for (int m = 0; m < G.vexnum; m++) for (int n = 0; n < G.vexnum; n++) if (m != n) G.Edge[m][n] = INF; else G.Edge[m][n] = 0; // 註意m==n時,設置為 0 System.out.println("請輸入每條邊依附的兩個頂點及權值:"); while (G.edgenum-- > 0) { u = scanner.next().charAt(0); v = scanner.next().charAt(0); w = scanner.nextInt(); i = locatevex(G, u);// 查找頂點 u 的存儲下標 j = locatevex(G, v);// 查找頂點 v 的存儲下標 if (i != -1 && j != -1) G.Edge[i][j] = w; //有向圖鄰接矩陣 else { System.out.println("輸入頂點信息錯!請重新輸入!"); G.edgenum++; // 本次輸入不算 } } } static void Floyd(AMGraph G) { // 用 Floyd 算法求有向網 G 中各對頂點 i 和 j 之間的最短路徑 int i, j, k; for (i = 0; i < G.vexnum; i++) // 各對結點之間初始已知路徑及距離 for (j = 0; j < G.vexnum; j++) { dist[i][j] = G.Edge[i][j]; if (dist[i][j] < INF && i != j) p[i][j] = i; // 如果 i 和 j 之間有弧,則將 j 的前驅置為 i else p[i][j] = -1; // 如果 i 和 j 之間無弧,則將 j 的前驅置為 -1 } for (k = 0; k < G.vexnum; k++) for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) { // 從 i 經 k 到 j 的一條路徑更短 dist[i][j] = dist[i][k] + dist[k][j]; // 更新dist[i][j] p[i][j] = p[k][j]; // 更改 j 的前驅 } } static void print(AMGraph G) { // 輸出鄰接矩陣 int i, j; for (i = 0; i < G.vexnum; i++) {//輸出最短距離數組 for (j = 0; j < G.vexnum; j++) System.out.print(dist[i][j] + "\t"); System.out.println(); } System.out.println(); for (i = 0; i < G.vexnum; i++) {//輸出前驅數組 for (j = 0; j < G.vexnum; j++) System.out.print(p[i][j] + "\t"); System.out.println(); } } static void DisplayPath(AMGraph G, int s, int t) { // 顯示最短路徑 if (p[s][t] != -1) { DisplayPath(G, s, p[s][t]); System.out.print(G.Vex[p[s][t]] + "-->"); } } public static void main(String[] args) { char start, destination; int u, v; AMGraph G = new AMGraph(); CreateAMGraph(G); Floyd(G); print(G); System.out.print("請依次輸入路徑的起點與終點的名稱:"); Scanner scanner = new Scanner(System.in); start = scanner.next().charAt(0); destination = scanner.next().charAt(0); u = locatevex(G, start); v = locatevex(G, destination); DisplayPath(G, u, v); System.out.println(G.Vex[v]); System.out.println("最短路徑的長度為:" + dist[u][v]); System.out.println(); } } class AMGraph { char Vex[] = new char[Floyd.MaxVnum]; int Edge[][] = new int[Floyd.MaxVnum][Floyd.MaxVnum]; int vexnum; // 頂點數 int edgenum; // 邊數 }
三 實現
白色為輸出,綠色為輸入。
到此這篇關於Java實現Floyd算法的示例代碼的文章就介紹到這瞭,更多相關Java Floyd算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!