Java控制台程序，打印的语句很多，直接看控制台输出更好理解。
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
int[][] testMatrix = {
{-1,-1,10,-1,30,100},
{-1,-1,5,-1,-1,-1},
{-1,-1,-1,50,-1,-1},
{-1,-1,-1,-1,0,10},
{-1,-1,-1,20,-1,60},
{-1,-1,-1,-1,-1,-1}
};
Dijkstra.dijkstra0(testMatrix,0);
}
}
package com.company;
public class Dijkstra {
/**
* 这就是著名的迪杰斯特拉算法，适用于有向图。
* 求的是某源点到所有其他顶点的最短路径问题。
* 从算法的变化图来看，该算法就是在已经找到最
* 短路径的顶点集合之外一个顶点，该顶点与已有
* 集合的顶点邻接，并且，邻接的边加上该集合中
* 邻接的点的最短路径以后最小的那个非该集合的
* 顶点加入到该集合中。
* 这是贪心算法思想的典型代表。
* 本实现的打印语句比较多，为的是直观地展现该
* 算法思想。
* @param sourceArray
* @param vertexId
*/
static public void dijkstra0(int[][] sourceArray,int vertexId) {
int arrayLength = sourceArray.length;
if (vertexId < 0 || vertexId > arrayLength - 1) {
System.out.println("输入顶点编号超出范围");
return;
}
//获取相对的最大值
int maxValue = 0;
for (int counter = 0;counter < arrayLength;counter++) {
for (int counter0 = 0;counter0 < arrayLength;counter0++) {
if (sourceArray[counter][counter0] < 0)continue;
else maxValue += sourceArray[counter][counter0];
}
}
//用来存储每个顶点的前驱顶点。
int[] preVertextArray = new int[arrayLength];
for (int counter = 0;counter < arrayLength;counter++)
preVertextArray[counter] = -1;
//这个用来表示已经找到最小路径的顶点集。
VertexPath[] minPathArray = new VertexPath[arrayLength];
int minPathPointer = 0;
//没有找到最小路径的顶点集合。
VertexPath[] equivocalVertexArray = new VertexPath[arrayLength];
int equivocalVertexPointer = 0;
//首先初始化没有找到最小路径的顶点集合，顺便把前驱数组初始化一下。
for (int counter = 0;counter < arrayLength;counter++) {
if (vertexId == counter) {
equivocalVertexArray[equivocalVertexPointer++] =
new VertexPath(counter,0);
preVertextArray[vertexId] = -1;
}
else {
equivocalVertexArray[equivocalVertexPointer++] =
new VertexPath(counter,sourceArray[vertexId][counter]);
if (sourceArray[vertexId][counter] > 0)
preVertextArray[counter] = vertexId;
}
}
//首先从还没有找到最短路径的集合中找到不是-1的也
// 不是maxValue的顶点，因为这些顶点是和已有最短
// 路径点集直接相连的顶点。从这些点中选择权值最小
// 的那个，添加到已有最短路径点集中。直到已有最短
// 路径点集满，出现maxValue或者-1权值的顶点为止。
while (minPathPointer < arrayLength) {
System.out.println("已有最小顶点的最小顶点序列");
for (int counter = 0;counter < minPathPointer;counter++) {
System.out.print("<" + minPathArray[counter].getVertexId() + "," + minPathArray[counter].getMinPathLenght() + ">");
}
System.out.println("\n没有选出最小顶点之前的非最小路径顶点序列");
for (int counter = 0;counter < equivocalVertexPointer;counter++) {
System.out.print("<" + equivocalVertexArray[counter].getVertexId() + "," + equivocalVertexArray[counter].getMinPathLenght() + ">");
}
System.out.println("\n即将刷新");
int firstMaxValue = maxValue;
int minVertexPointer = 0;
//找出没有最短路径的点集中的最小权的顶点。
for (int counter = 0;counter < equivocalVertexPointer;counter++) {
if (equivocalVertexArray[counter].getMinPathLenght() >= 0 &&
equivocalVertexArray[counter].getMinPathLenght() < firstMaxValue) {
minVertexPointer = counter;
firstMaxValue = equivocalVertexArray[counter].getMinPathLenght();
}
}
//然后和没有最短路径的数组的大边界元素交换
// ，这样做的好处是可以节省空间和避免不必要的遍历。
if (minVertexPointer != equivocalVertexPointer - 1) {
VertexPath tempNode = equivocalVertexArray[equivocalVertexPointer - 1];
equivocalVertexArray[equivocalVertexPointer - 1] = equivocalVertexArray[minVertexPointer];
equivocalVertexArray[minVertexPointer] = tempNode;
}
minPathArray[minPathPointer] = equivocalVertexArray[equivocalVertexPointer - 1];
minPathPointer++;
equivocalVertexPointer--;
System.out.println("已经选出的最小顶点序列");
for (int counter = 0;counter < minPathPointer;counter++) {
System.out.print("<" + minPathArray[counter].getVertexId() + "," + minPathArray[counter].getMinPathLenght() + ">");
}
System.out.println("\n调整之前的非最小路径定点");
for (int counter = 0;counter < equivocalVertexPointer;counter++) {
System.out.print("<" + equivocalVertexArray[counter].getVertexId() + "," + equivocalVertexArray[counter].getMinPathLenght() + ">");
}
System.out.println();
//已有最短路径的顶点集
for (int counter = 0;counter < minPathPointer && minPathArray[counter].getMinPathLenght() >= 0;counter++) {
System.out.println("现在依据<" + minPathArray[counter].getVertexId() +
"," + minPathArray[counter].getMinPathLenght() + ">进行刷新");
//还没有最短路径的顶点集合。
for (int counter0 = 0;counter0 < equivocalVertexPointer;counter0++) {
System.out.println("现在调整未调整的顶点<" + equivocalVertexArray[counter0].getVertexId() +
"," + equivocalVertexArray[counter0].getMinPathLenght() + ">");
//这是相临边，有可能是无限大的，此时直接跳过，
// 不过这里处于打印的需要，我还是写了else。
int edgeLength = sourceArray[minPathArray[counter].getVertexId()]
[equivocalVertexArray[counter0].getVertexId()];
//此时为可达的情况下，也就是有相邻的边的时候。
if (edgeLength > 0) {
System.out.println("可达边长度为:" + edgeLength);
//因为这里认为边权为负代表无穷大。
if (equivocalVertexArray[counter0].getMinPathLenght() < 0)
equivocalVertexArray[counter0].setMinPathLenght(maxValue);
if (edgeLength + minPathArray[counter].getMinPathLenght() <
equivocalVertexArray[counter0].getMinPathLenght()) {
//找到更小的就更新边权值
System.out.println(edgeLength + " + " + minPathArray[counter].getMinPathLenght()
+ "小于" + equivocalVertexArray[counter0].getMinPathLenght());
preVertextArray[equivocalVertexArray[counter0].getVertexId()]
= minPathArray[counter].getVertexId();
equivocalVertexArray[counter0].setMinPathLenght(edgeLength
+ minPathArray[counter].getMinPathLenght());
System.out.println("顶点" + equivocalVertexArray[counter0].getVertexId()
+ "权被更新为" + (edgeLength
+ minPathArray[counter].getMinPathLenght()));
} else {
System.out.println(edgeLength + " + " + minPathArray[counter].getMinPathLenght()
+ "与" + equivocalVertexArray[counter0].getMinPathLenght() + "相比");
System.out.println("没使路径更小，舍去!");
}
} else System.out.println("不可达");
}
}
System.out.println("调整之后的最小路径顶点");
for (int counter = 0;counter < minPathPointer;counter++) {
System.out.print("<" + minPathArray[counter].getVertexId() + "," + minPathArray[counter].getMinPathLenght() + ">");
}
System.out.println("\n调整之后的非最小路径定点");
for (int counter = 0;counter < equivocalVertexPointer;counter++) {
System.out.print("<" + equivocalVertexArray[counter].getVertexId() + "," + equivocalVertexArray[counter].getMinPathLenght() + ">");
}
System.out.println("\n结束刷新\n");
}
System.out.println("结果集为:");
int[] pathStack = new int[arrayLength];
for (int counter = 0;counter < arrayLength;counter++) {
if (counter == vertexId)continue;
int pathStackTopPointer = -1;
int preIndex = counter;
while (preVertextArray[preIndex] >= 0) {
pathStack[++pathStackTopPointer] = preIndex;
preIndex = preVertextArray[preIndex];
}
pathStack[++pathStackTopPointer] = preIndex;
System.out.print("(" + vertexId + "," + counter + "):");
if (pathStack[pathStackTopPointer] != vertexId)
System.out.print("不可达");
else {
while (pathStackTopPointer > -1) {
if (counter == pathStack[pathStackTopPointer])
System.out.print(pathStack[pathStackTopPointer--]);
else System.out.print(pathStack[pathStackTopPointer--] + "-->");
}
}
System.out.println();
}
}
}
package com.company;
public class VertexPath {
private int vertexId;
private int minPathLenght;
public VertexPath(int vertexId, int minPathLenght) {
this.vertexId = vertexId;
this.minPathLenght = minPathLenght;
}
public int getMinPathLenght() {
return minPathLenght;
}
public void setMinPathLenght(int minPathLenght) {
this.minPathLenght = minPathLenght;
}
public int getVertexId() {
return vertexId;
}
}
输出
已有最小顶点的最小顶点序列
没有选出最小顶点之前的非最小路径顶点序列
<0,0><1,-1><2,10><3,-1><4,30><5,100>
即将刷新
已经选出的最小顶点序列
<0,0>
调整之前的非最小路径定点
<5,100><1,-1><2,10><3,-1><4,30>
现在依据<0,0>进行刷新
现在调整未调整的顶点<5,100>
可达边长度为:100
100 + 0与100相比
没使路径更小，舍去!
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<2,10>
可达边长度为:10
10 + 0与10相比
没使路径更小，舍去!
现在调整未调整的顶点<3,-1>
不可达
现在调整未调整的顶点<4,30>
可达边长度为:30
30 + 0与30相比
没使路径更小，舍去!
调整之后的最小路径顶点
<0,0>
调整之后的非最小路径定点
<5,100><1,-1><2,10><3,-1><4,30>
结束刷新
已有最小顶点的最小顶点序列
<0,0>
没有选出最小顶点之前的非最小路径顶点序列
<5,100><1,-1><2,10><3,-1><4,30>
即将刷新
已经选出的最小顶点序列
<0,0><2,10>
调整之前的非最小路径定点
<5,100><1,-1><4,30><3,-1>
现在依据<0,0>进行刷新
现在调整未调整的顶点<5,100>
可达边长度为:100
100 + 0与100相比
没使路径更小，舍去!
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<4,30>
可达边长度为:30
30 + 0与30相比
没使路径更小，舍去!
现在调整未调整的顶点<3,-1>
不可达
现在依据<2,10>进行刷新
现在调整未调整的顶点<5,100>
不可达
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<4,30>
不可达
现在调整未调整的顶点<3,-1>
可达边长度为:50
50 + 10小于285
顶点3权被更新为60
调整之后的最小路径顶点
<0,0><2,10>
调整之后的非最小路径定点
<5,100><1,-1><4,30><3,60>
结束刷新
已有最小顶点的最小顶点序列
<0,0><2,10>
没有选出最小顶点之前的非最小路径顶点序列
<5,100><1,-1><4,30><3,60>
即将刷新
已经选出的最小顶点序列
<0,0><2,10><4,30>
调整之前的非最小路径定点
<5,100><1,-1><3,60>
现在依据<0,0>进行刷新
现在调整未调整的顶点<5,100>
可达边长度为:100
100 + 0与100相比
没使路径更小，舍去!
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<3,60>
不可达
现在依据<2,10>进行刷新
现在调整未调整的顶点<5,100>
不可达
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<3,60>
可达边长度为:50
50 + 10与60相比
没使路径更小，舍去!
现在依据<4,30>进行刷新
现在调整未调整的顶点<5,100>
可达边长度为:60
60 + 30小于100
顶点5权被更新为90
现在调整未调整的顶点<1,-1>
不可达
现在调整未调整的顶点<3,60>
可达边长度为:20
20 + 30小于60
顶点3权被更新为50
调整之后的最小路径顶点
<0,0><2,10><4,30>
调整之后的非最小路径定点
<5,90><1,-1><3,50>
结束刷新
已有最小顶点的最小顶点序列
<0,0><2,10><4,30>
没有选出最小顶点之前的非最小路径顶点序列
<5,90><1,-1><3,50>
即将刷新
已经选出的最小顶点序列
<0,0><2,10><4,30><3,50>
调整之前的非最小路径定点
<5,90><1,-1>
现在依据<0,0>进行刷新
现在调整未调整的顶点<5,90>
可达边长度为:100
100 + 0与90相比
没使路径更小，舍去!
现在调整未调整的顶点<1,-1>
不可达
现在依据<2,10>进行刷新
现在调整未调整的顶点<5,90>
不可达
现在调整未调整的顶点<1,-1>
不可达
现在依据<4,30>进行刷新
现在调整未调整的顶点<5,90>
可达边长度为:60
60 + 30与90相比
没使路径更小，舍去!
现在调整未调整的顶点<1,-1>
不可达
现在依据<3,50>进行刷新
现在调整未调整的顶点<5,90>
可达边长度为:10
10 + 50小于90
顶点5权被更新为60
现在调整未调整的顶点<1,-1>
不可达
调整之后的最小路径顶点
<0,0><2,10><4,30><3,50>
调整之后的非最小路径定点
<5,60><1,-1>
结束刷新
已有最小顶点的最小顶点序列
<0,0><2,10><4,30><3,50>
没有选出最小顶点之前的非最小路径顶点序列
<5,60><1,-1>
即将刷新
已经选出的最小顶点序列
<0,0><2,10><4,30><3,50><5,60>
调整之前的非最小路径定点
<1,-1>
现在依据<0,0>进行刷新
现在调整未调整的顶点<1,-1>
不可达
现在依据<2,10>进行刷新
现在调整未调整的顶点<1,-1>
不可达
现在依据<4,30>进行刷新
现在调整未调整的顶点<1,-1>
不可达
现在依据<3,50>进行刷新
现在调整未调整的顶点<1,-1>
不可达
现在依据<5,60>进行刷新
现在调整未调整的顶点<1,-1>
不可达
调整之后的最小路径顶点
<0,0><2,10><4,30><3,50><5,60>
调整之后的非最小路径定点
<1,-1>
结束刷新
已有最小顶点的最小顶点序列
<0,0><2,10><4,30><3,50><5,60>
没有选出最小顶点之前的非最小路径顶点序列
<1,-1>
即将刷新
已经选出的最小顶点序列
<0,0><2,10><4,30><3,50><5,60><1,-1>
调整之前的非最小路径定点
现在依据<0,0>进行刷新
现在依据<2,10>进行刷新
现在依据<4,30>进行刷新
现在依据<3,50>进行刷新
现在依据<5,60>进行刷新
调整之后的最小路径顶点
<0,0><2,10><4,30><3,50><5,60><1,-1>
调整之后的非最小路径定点
结束刷新
结果集为:
(0,1):不可达
(0,2):0-->2
(0,3):0-->4-->3
(0,4):0-->4
(0,5):0-->4-->3-->5
