一问题描述

求节点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;
 // 边数
}
    

三实现

白色为输出，绿色为输入。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！