Java如何实现Dijkstra算法，代码是怎样

一问题描述

小明为位置1，求他到其他各顶点的距离。

二实现

package graph.dijkstra;
    
 
import java.util.Scanner;
    
import java.util.Stack;

 
public class Dijkstra {
    
    static final int MaxVnum = 100;
      // 顶点数最大值
    static final int INF = 0x3f3f3f3f;
     //无穷大
    static final int dist[] = new int[MaxVnum];
     // 最短距离
    static final int p[] = new int[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++)
                G.Edge[m][n] = INF;
    
 
        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 print(AMGraph G) {
     // 输出邻接矩阵
        System.out.println("图的邻接矩阵为：");
    
        for (int i = 0;
     i  G.vexnum;
 i++) {
    
            for (int j = 0;
     j  G.vexnum;
     j++)
                System.out.print(G.Edge[i][j] + "\t");
    
            System.out.println();

        }

    }

 
    public static void main(String[] args) {
    
        AMGraph G = new AMGraph();
    
        int st;
    
        char u;
    
        CreateAMGraph(G);
    
        System.out.println("请输入源点的信息:");
    
        Scanner scanner = new Scanner(System.in);
    
        u = scanner.next().charAt(0);
    
        ;
    
        st = locatevex(G, u);
    //查找源点u的存储下标
        Dijkstra(G, st);
    
        System.out.println("小明所在的位置:" + u);
    
 
        for (int i = 0;
     i  G.vexnum;
 i++) {
    
            System.out.print("小明:" + u + " - " + "要去的位置:" + G.Vex[i]);
    
 
            if (dist[i] == INF)
                System.out.print(" sorry,无路可达");
    
            else
                System.out.println(" 最短距离为:" + dist[i]);

        }
    
        findpath(G, u);

    }

 
    public static void Dijkstra(AMGraph G, int u) {
    
        for (int i = 0;
     i  G.vexnum;
 i++) {
    
            dist[i] = G.Edge[u][i];
     //初始化源点u到其他各个顶点的最短路径长度
            flag[i] = false;
    
            if (dist[i] == INF)
                p[i] = -1;
     //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
            else
                p[i] = u;
 //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
        }
    
        dist[u] = 0;
    
        flag[u] = true;
       //初始时，集合S中只有一个元素：源点u
        for (int i = 0;
     i  G.vexnum;
 i++) {
    
            int temp = INF, t = u;
    
            for (int j = 0;
     j  G.vexnum;
     j++) //在集合V-S中寻找距离源点u最近的顶点t
                if (!flag[j] &
    &
 dist[j]  temp) {
    
                    t = j;
    
                    temp = dist[j];

                }
    
            if (t == u) return;
     //找不到t，跳出循环
            flag[t] = true;
      //否则，将t加入集合
            for (int j = 0;
     j  G.vexnum;
     j++)//更新V-S中与t相邻接的顶点到源点u的距离
                if (!flag[j] &
    &
     G.Edge[t][j]  INF)
                    if (dist[j] >
 (dist[t] + G.Edge[t][j])) {
    
                        dist[j] = dist[t] + G.Edge[t][j];
    
                        p[j] = t;

                    }

        }

    }

 
    public static void findpath(AMGraph G, char u) {
    
        int x;
    
        StackInteger>
     S = new Stack>
    ();
    
        System.out.println("源点为：" + u);
    
 
        for (int i = 0;
     i  G.vexnum;
 i++) {
    
            x = p[i];
    
            if (x == -1 &
    &
 u != G.Vex[i]) {
    
                System.out.println("源点到其它各顶点最短路径为：" + u + "--" + G.Vex[i] + "    sorry,无路可达");
    
                continue;

            }

            while (x != -1) {
    
                S.push(x);
    
                x = p[x];

            }
    
            System.out.println("源点到其它各顶点最短路径为：");

            while (!S.empty()) {
    
                System.out.print(G.Vex[S.peek()] + "--");
    
                S.pop();

            }
    
            System.out.println(G.Vex[i] + "    最短距离为：" + dist[i]);

        }

    }

}

 
class AMGraph {
    
    char Vex[] = new char[Dijkstra.MaxVnum];
    
    int Edge[][] = new int[Dijkstra.MaxVnum][Dijkstra.MaxVnum];
    
    int vexnum;
     // 顶点数
    int edgenum;
 // 边数
}
    

三测试

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