1 Star 0 Fork 0

besti1923/JAVA

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
DijstraAlgorithm.java 6.05 KB
一键复制 编辑 原始数据 按行查看 历史
yifei 提交于 5年前 . shiyan9
package text.java;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class DijstraAlgorithm {
public static void main(String[] args) {
int vertexNum = 5;
char[] vertexs = new char[] { 'A', 'B', 'C', 'D', 'E' };
int[][] matrix = new int[][] { { 0, 10, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 5 },
{ Integer.MAX_VALUE / 2, 5, 1, Integer.MAX_VALUE / 2, 5 },
{ Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 0, 4, Integer.MAX_VALUE / 2 },
{ 7, Integer.MAX_VALUE / 2, 6, 7, Integer.MAX_VALUE / 2 },
{ Integer.MAX_VALUE / 2, 3, 9, 2, 5 } }; // matrix[i][j]为0表示i==j,matrix[i][j]为Integer.MAX_VALUE/2表示两个顶点不是图的边,否则表示边的权值
Graph g = new Graph(vertexNum, vertexs, matrix);
Scanner sc = new Scanner(System.in);
int srcIndex;
do{
System.out.print("请输入源点索引(0~4):");
srcIndex = sc.nextInt();
}while(srcIndex < 0 || srcIndex > 4);
System.out.println(g.vertexs[srcIndex] + "作为源点");
Info info = dijkstra(g, srcIndex); // 指定将索引为srcIndex的顶点作为源点
for(int i : info.pathSerials){
System.out.print(g.vertexs[i] + " ");
}
System.out.println();
int index = 0;
for(int[] path : info.paths){
for(int i : path){
System.out.print(g.vertexs[i]);
}
System.out.println(": " + info.distances[index++]);
}
sc.close();
}
// 通过迪杰斯特拉(Dijkstra)算法求以vertex[srcIndex]顶点作为源点到其余各顶点的最短路径
public static Info dijkstra(Graph g, int srcIndex) {
if(srcIndex < 0 || srcIndex >= g.vertexNum){
return null;
}
int[] pathSerials = new int[g.vertexNum]; // pathSerials[i]表示从源点到顶点i的最短路径(即若P(srcIndex,j)={V(srcIndex)...Vk...Vs...Vj}是从源点srcIndex到j的最短路径,则有P(srcIndex,j)=P(srcIndex,k)+P(k,s)+P(s,j))
int[] path = new int[g.vertexNum]; // path[i]表示从源点到顶点i(i为vertexs中的索引)的最短路径中顶点i的前驱顶点
int index = 0;
pathSerials[index] = srcIndex; // 源点加入序列中
g.visited[srcIndex] = true; // 源点已在最短路径序列中
Arrays.fill(path, -1); // -1表示顶点没有前驱顶点
int[] distances = new int[g.vertexNum]; // distances[i]表示从源点到顶点i(i为vertexs中的索引)的当前最短路径长度
for (int i = 0; i < g.vertexNum; i++) {
// 初始化distances为其余顶点到源点的权值
distances[i] = g.matrix[srcIndex][i];
}
int minIndex = srcIndex;
while (minIndex != -1) { // 仍有未加入到最短路径序列中的顶点
index++;
for (int i = 0; i < g.vertexNum; i++) {
if (!g.visited[i]) { // 更新仍未加入到最短路径序列中的顶点的从源点到它的值
// 这些仍未加入到最短路径序列中的顶点的distances[i]值为(刚加入的顶点minIndex的distances[minIndex]与minIndex到顶点i之和)与(顶点minIndex刚加入之前源点到i的距离值distances[i])两者之间的较小者
distances[i] = Math.min(distances[i], distances[minIndex] + g.matrix[minIndex][i]);
// 如果当前顶点i的distances[i]值为新加入的顶点minIndex,则顶点i的前驱为minIndex,否则不变
if(distances[i] == distances[minIndex] + g.matrix[minIndex][i] && distances[i] != Integer.MAX_VALUE / 2){ // distances[i] != Integer.MAX_VALUE / 2表示仍不可达,就没有前驱
path[i] = minIndex;
}
}
}
minIndex = indexOf(g, distances); // 选出的最小顶点
if(minIndex == -1){
break;
}
pathSerials[index] = minIndex; // 刚选出的最小顶点加入到最短路径序列中
g.visited[minIndex] = true;
}
return new Info(distances, pathSerials, getPathOfAll(path, pathSerials));
}
// 找到图中仍未加入到最短路径序列顶点集中到源点距离最小的顶点的索引
public static int indexOf(Graph g, int[] distances) {
int min = Integer.MAX_VALUE / 3;
int minIndex = -1; // 当前数组distances剩余元素最小值(-1表示无剩余元素)--剩余元素就是仍未加入到最短路径序列中的顶点
for(int i = 0; i < g.vertexNum; i++){
if(!g.visited[i]){ // 如果i顶点仍未加入到最短路径序列中
if(distances[i] < min){
min = distances[i];
minIndex = i;
}
}
}
return minIndex;
}
// 得到指定顶点i的从源点到顶点i的最短路径(均以顶点集vertexs中索引表示)
public static int[] getPath(int[] path, int i){
Stack<Integer> s = new Stack<Integer>();
s.push(i);
int pre = path[i];
while(pre != -1){
s.push(pre);
pre = path[pre];
}
int size = s.size();
int[] pathOfVertex = new int[size];
while(!s.isEmpty()){
pathOfVertex[size - s.size()] = s.pop();
}
return pathOfVertex;
}
public static ArrayList<int[]> getPathOfAll(int[] path, int[] pathSerials){
ArrayList<int[]> paths = new ArrayList<int[]>();
for(int i = 0; i < pathSerials.length; i++){
paths.add(getPath(path, i));
}
return paths;
}
public static class Graph{
private int vertexNum;
private char[] vertexs;
private int[][] matrix;
private boolean visited[];
public Graph(int vertexNum, char[] vertexs, int[][] matrix){
this.vertexNum = vertexNum;
this.vertexs = vertexs;
this.matrix = matrix;
visited = new boolean[vertexNum];
}
}
public static class Info{
private int[] distances; // 源点到各个顶点的最短距离
private int[] pathSerials; // 整个最短路径序列
private ArrayList<int[]> paths; // 源点到各个顶点的确切最短路径序列
public Info(int[] distances, int[] pathSerials, ArrayList<int[]> paths) {
this.distances = distances;
this.pathSerials = pathSerials;
this.paths = paths;
}
}
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
Java
1
https://gitee.com/besti1923/java.git
git@gitee.com:besti1923/java.git
besti1923
java
JAVA
master

搜索帮助