Java实现Dijkstra算法的示例代码
短信预约 -IT技能 免费直播动态提醒
一 问题描述
小明为位置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; // 边数
}
三 测试
到此这篇关于Java实现Dijkstra算法的示例代码的文章就介绍到这了,更多相关Java Dijkstra算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341