您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java如何實現(xiàn)Floyd算法”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學(xué)習(xí)“Java如何實現(xiàn)Floyd算法”吧!
求節(jié)點0到節(jié)點2的最短路徑。
package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 頂點數(shù)最大值 static final int INF = 0x3f3f3f3f; //無窮大 static final int dist[][] = new int[MaxVnum][MaxVnum]; // 最短距離 static final int p[][] = new int[MaxVnum][MaxVnum]; // 前驅(qū)數(shù)組 static final boolean flag[] = new boolean[MaxVnum]; // 如果 s[i] 等于 true,說明頂點 i 已經(jīng)加入到集合 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("請輸入頂點數(shù):"); G.vexnum = scanner.nextInt(); System.out.println("請輸入邊數(shù):"); G.edgenum = scanner.nextInt(); System.out.println("請輸入頂點信息:"); // 輸入頂點信息,存入頂點信息數(shù)組 for (int k = 0; k < G.vexnum; k++) { G.Vex[k] = scanner.next().charAt(0); } //初始化鄰接矩陣所有值為0,如果是網(wǎng),則初始化鄰接矩陣為無窮大 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時,設(shè)置為 0 System.out.println("請輸入每條邊依附的兩個頂點及權(quán)值:"); 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 算法求有向網(wǎng) G 中各對頂點 i 和 j 之間的最短路徑 int i, j, k; for (i = 0; i < G.vexnum; i++) // 各對結(jié)點之間初始已知路徑及距離 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 的前驅(qū)置為 i else p[i][j] = -1; // 如果 i 和 j 之間無弧,則將 j 的前驅(qū)置為 -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 經(jīng) k 到 j 的一條路徑更短 dist[i][j] = dist[i][k] + dist[k][j]; // 更新dist[i][j] p[i][j] = p[k][j]; // 更改 j 的前驅(qū) } } static void print(AMGraph G) { // 輸出鄰接矩陣 int i, j; for (i = 0; i < G.vexnum; i++) {//輸出最短距離數(shù)組 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++) {//輸出前驅(qū)數(shù)組 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; // 頂點數(shù) int edgenum; // 邊數(shù) }
白色為輸出,綠色為輸入。
到此,相信大家對“Java如何實現(xiàn)Floyd算法”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。