Java 图的最短路径dijstra(迪杰斯特拉)算法和拓扑排序
2018-05-21 本文已影响21人
磊_lei
一、图的最短路径
从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径
图的最短路径
图的最短路径有许多重要的应用。
例如：上图中v0-v8有9个点，可以看做不同的地点，现在要规划出v0到其它某个点地点的最短路线规划
构建最短路径中比较常见的一种算法即为dijstra(迪杰斯特拉)算法
二、dijstra(迪杰斯特拉)算法
算法思路：
- dijstra算法思路有点类似前一篇文章中的prim算法，先构建图的邻接矩阵，然后定义一个临时的一维数组，一维数组用来存储v0到每个顶点的最短路径
- 将一维数组初始化成v0到每个顶点的值。其次定义另外一个数组用来存储已经访问过的顶点
- 在临时一维数组中找到未被访问且最短的一条路径
- 将找到最短路径的顶点与该顶点可访问边进行遍历，若最短路径与边之和小于一维数组中存储的最短路径，则将这个和覆盖成这个顶点的最短路径
- 循环3，4直至遍历完所有顶点为止
- 构建邻接矩阵
// 初始化图
int[] graph0 = new int[]{0, 1, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
int[] graph1 = new int[]{1, 0, 3, 7, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
int[] graph2 = new int[]{5, 3, 0, MAX_WEIGHT, 1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
int[] graph3 = new int[]{MAX_WEIGHT, 7, MAX_WEIGHT, 0, 2, MAX_WEIGHT, 3, MAX_WEIGHT, MAX_WEIGHT};
int[] graph4 = new int[]{MAX_WEIGHT, 5, 1, 2, 0, 3, 6, 9, MAX_WEIGHT};
int[] graph5 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 7, MAX_WEIGHT, 3, 0, MAX_WEIGHT, 5, MAX_WEIGHT};
int[] graph6 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 3, 6, MAX_WEIGHT, 0, 2, 7};
int[] graph7 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 5, 2, 0, 4};
int[] graph8 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 5, 4, 0};
- 算法代码
/**
* 图的最短路径(图中两个顶点的最短距离)，迪杰斯特拉算法
* 算法思想：类似prim算法，定义一个一维数组，用来存储V0到某点的最短路径
*/
public void shortestPathDijstra() {
// 定义一维数组用来存储V0到每个点的最短路径，找到比原来更短的则直接覆盖
int[] paths = new int[vertexSize];
// 先将数组初始化
System.arraycopy(matrix[0], 0, paths, 0, vertexSize);
isVisited[0] = true;
for (int i = 1; i < vertexSize; i++) {
// 在已经存在的路径中找到一条未被访问且最短的路径
int min = MAX_WEIGHT;
int minIndex = -1;
for (int j = 1; j < vertexSize; j++) {
if (!isVisited[j] && paths[j] < min) {
min = paths[j];
minIndex = j;
}
}
if (minIndex == -1) {
continue;
}
isVisited[minIndex] = true;
// 找到的最短路径节点的可使用边中，判断是否比已经存在的最短路径短，是则进行覆盖
for (int k = 1; k < vertexSize; k++) {
if (!isVisited[k] && (min + matrix[minIndex][k] < paths[k])) {
paths[k] = min + matrix[minIndex][k];
}
}
}
for (int i = 1; i < vertexSize; i++) {
System.out.println("V0到V" + i + "的最短路径为：" + paths[i]);
}
}
- 即可得到v0到每个点的最短路径的值
dijstra最短路径
三、拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
对以下有向图进行拓扑排序，顶点可以看待成每项不同的任务，有的任务可以直接执行，例如v0、v1、v3，有的任务得等到上级任务全部执行完成才可执行，例如v4必须等到v0和v1都完成之后才可执行
拓扑排序
排序思路：
- 观察可以发现顶点入度为0则代表可以直接执行
- 完成一个任务之后可消除出度的边，即他的next节点则少了一个入度
- 带next节点入度也为0之后就可执行
- 循环1，2，3遍历完所有的顶点即可排序完成
排序代码：
- 构建每个顶点的邻接表
拓扑排序邻接点
- 算法代码
/**
* 拓扑排序
* 思路：定义一个栈，存放入度为0的节点，入度为0则代表可以执行，执行之后则出度的那个节点就减少一个入度，循环直至栈为空
*/
private void topologicaSort() {
Stack<Integer> stack = new Stack<>();
// 先将入度为0 的节点压入栈中
for (int i = 0; i < adjList.length; i++) {
if (adjList[i].in == 0) {
stack.push(i);
}
}
int count = 0;
// 循环出栈输出，直至栈为空
while (!stack.isEmpty()) {
int index = stack.pop();
System.out.println("顶点：" + adjList[index].data);
count++;
for (EdgeNode edgeNode = adjList[index].firstEdge; edgeNode != null; edgeNode = edgeNode.next) {
if (--adjList[edgeNode.adjVert].in == 0) {
// 若输出之后的顶点入度也没0，则压入栈中
stack.push(edgeNode.adjVert);
}
}
}
if (count != numVertexes) {
System.out.println("拓扑排序失败！！！！");
}
}
