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算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！