我要评论
说明
闵老师的文章链接： 日撸 java 三百行（总述）_minfanphd的博客-csdn博客
自己也把手敲的代码放在了github上维护：https://github.com/fulisha-ok/sampledata
day38
1.dijkstra 算法思路分析
假设以顶点0出发
（1）0到各个顶点距离为：<0,1> 6；<0,2> 2 ；<0,3> ∞；选取最小距离<0,2> 2
（2）加入<0,2>一条边，看0到剩余顶点距离：
<0,1>: 原<0,1> 6，在加入<0,2>，则可以借助<0,2>，<0,2><2,1> 5；选取最小距离5
<0,3>：原<0,3> ∞，在加入<0,2>，<0,2><2,3> 7；选取最小距离7
比较5和7选取最小的距离5 0->1: 5
（3）加入<0,2><2,1>边，看0到剩余顶点的距离
<0,3>：原<0,2><2,3> 7，在加入<2,1>，<0,2><2,1><1,3>7; 选取最小距离<0,2><2,3> 7
节点遍历完，找到0到各点最短距离 0->3: 7
在这个过程中进一步思考：
在实现这个过程中需要借助一些数组来存储数据：
开始顶点到每一个顶点的最短距离需要有一个数组来存储，并且在每循环一次都需要检查这个数组是否需要更新
开始顶点到某个顶点不一定是直连路径，则需要存储开始顶点到某个顶点的路径，则也需要一个数组来存储路径。
顶点是否已经确定为最短路径结点，需要一个数组来做一个标志。
2.prim 算法思路分析
prim算法为最小生成树，过程：任意选一个顶点（如选0顶点）
从0顶点到与之相连的结点之间距离最短的顶点，图中为2
在0，2结点中选择距离最短的结点，则为 1 节点
在0，1，2结点中选择距离最短的结点，则为3节点
当结点树n = 边树n-1即构建成功
3.对比
dijkstra 算法是求单源最短路径，可以算出开始顶点到其他顶点的最短路径，但是如果权重有负数，则dijstra并不能计算出正确的结果。而prim算法是构建最小生成树的一种策略。
dijkstra 求单源最短路径时，我们要给定一个顶点，去找到其他结点的最短路径，而最小生成树是任意选择一个顶点开始。
dijkstra 算法适用于有向图，而prim更适合无向图（我认为主要是有向图在两个节点来回可能权重不同）
4.代码
- 在dijkstra中主要分为三个for循环，一个大的for循环：一次循环就可以确定从v0顶点到某个顶点的最短路径，在大循环中的第一个循环是找出v0结点到剩余未访问结点中的最短路径，第三个循环是：已经确定某个顶点是最短路径，去更新tempdistancearray，tempparentarray这两个数组。
public int[] dijikstra(int parasource) {
// step 1. initialize.
int[] tempdistancearray = new int[numnodes];
for (int i = 0; i < numnodes; i++) {
tempdistancearray[i] = weightmatrix.getvalue(parasource, i);
}
int[] tempparentarray = new int[numnodes];
arrays.fill(tempparentarray, parasource);
// -1 for no parent.
tempparentarray[parasource] = -1;
// visited nodes will not be considered further.
boolean[] tempvisitedarray = new boolean[numnodes];
tempvisitedarray[parasource] = true;
// step 2. main loops.
int tempmindistance;
int tempbestnode = -1;
for (int i = 0; i < numnodes - 1; i++) {
// step 2.1 find out the best next node.
tempmindistance = integer.max_value;
for (int j = 0; j < numnodes; j++) {
// this node is visited.
if (tempvisitedarray[j]) {
continue;
}
if (tempmindistance > tempdistancearray[j]) {
tempmindistance = tempdistancearray[j];
tempbestnode = j;
}
}
tempvisitedarray[tempbestnode] = true;
// step 2.2 prepare for the next round.
for (int j = 0; j < numnodes; j++) {
// this node is visited.
if (tempvisitedarray[j]) {
continue;
}
// this node cannot be reached.
if (weightmatrix.getvalue(tempbestnode, j) >= max_distance) {
continue;
}
if (tempdistancearray[j] > tempdistancearray[tempbestnode]
+ weightmatrix.getvalue(tempbestnode, j)) {
// change the distance.
tempdistancearray[j] = tempdistancearray[tempbestnode]
+ weightmatrix.getvalue(tempbestnode, j);
// change the parent.
tempparentarray[j] = tempbestnode;
}
}
// for test
system.out.println("the distance to each node: " + arrays.tostring(tempdistancearray));
system.out.println("the parent of each node: " + arrays.tostring(tempparentarray));
}
// step 3. output for debug.
system.out.println("finally");
system.out.println("the distance to each node: " + arrays.tostring(tempdistancearray));
system.out.println("the parent of each node: " + arrays.tostring(tempparentarray));
return tempdistancearray;
}
- 在prim算法中，与dijkstra算法最大的区别在与第三个循环中，在更新tempdistancearray是累加之前的边，而在prim算法中则不需要累加，只需要判断从这个已选结点出发到其他结点的距离是否需要更新
public int prim() {
// step 1. initialize.
// any node can be the source.
int tempsource = 0;
int[] tempdistancearray = new int[numnodes];
for (int i = 0; i < numnodes; i++) {
tempdistancearray[i] = weightmatrix.getvalue(tempsource, i);
}
int[] tempparentarray = new int[numnodes];
arrays.fill(tempparentarray, tempsource);
// -1 for no parent.
tempparentarray[tempsource] = -1;
// visited nodes will not be considered further.
boolean[] tempvisitedarray = new boolean[numnodes];
tempvisitedarray[tempsource] = true;
// step 2. main loops.
int tempmindistance;
int tempbestnode = -1;
for (int i = 0; i < numnodes - 1; i++) {
// step 2.1 find out the best next node.
tempmindistance = integer.max_value;
for (int j = 0; j < numnodes; j++) {
// this node is visited.
if (tempvisitedarray[j]) {
continue;
}
if (tempmindistance > tempdistancearray[j]) {
tempmindistance = tempdistancearray[j];
tempbestnode = j;
}
}
tempvisitedarray[tempbestnode] = true;
// step 2.2 prepare for the next round.
for (int j = 0; j < numnodes; j++) {
// this node is visited.
if (tempvisitedarray[j]) {
continue;
}
// this node cannot be reached.
if (weightmatrix.getvalue(tempbestnode, j) >= max_distance) {
continue;
}
// attention: the difference from the dijkstra algorithm.
if (tempdistancearray[j] > weightmatrix.getvalue(tempbestnode, j)) {
// change the distance.
tempdistancearray[j] = weightmatrix.getvalue(tempbestnode, j);
// change the parent.
tempparentarray[j] = tempbestnode;
}
}
// for test
system.out.println(
"the selected distance for each node: " + arrays.tostring(tempdistancearray));
system.out.println("the parent of each node: " + arrays.tostring(tempparentarray));
}
int resultcost = 0;
for (int i = 0; i < numnodes; i++) {
resultcost += tempdistancearray[i];
}
// step 3. output for debug.
system.out.println("finally");
system.out.println("the parent of each node: " + arrays.tostring(tempparentarray));
system.out.println("the total cost: " + resultcost);
return resultcost;
}
-
单元测试
-
dijkstra算法（从顶点0出发）
-
prim算法
发表评论