二 代码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算法的详细内容。