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;
       Stack<Integer> 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; // 边数
}

三 测试

来源：https://blog.csdn.net/chengqiuming/article/details/125666127