在求解单源路径问题时存在一个简单的算法,这个算法通称Dijkstra算法,这个算法是基于贪心法的。算法课上尝试编写了这样一个算法,代码如下:
package com.sailor.greedy;
import java.util.LinkedList;
import java.util.List;
/**
* 单源最短路径问题
*
* @author Sailor
*
*/
public class ShortestPaths {
private static String showPath[] = { "", "", "", "", "", "" };
// 返回图的最短路径
public static int[] getShortPath(int path[][]) {
LinkedList<Integer> savePath = new LinkedList<Integer>();// 用于保存已添加进来的节点
int mark = 1;
int shortestPath[] = new int[path.length];
for (int i = 0; i < shortestPath.length; i++) {
shortestPath[i] = -1;
}
savePath.add(new Integer(0));
if (savePath.size() == 1) {
int num = savePath.getLast().intValue();
int minIndex = 0;
for (int j = 0; j < shortestPath.length; j++) {
shortestPath[j] = path[num][j];
if (shortestPath[j] >= 0) {
showPath[j] = "1-->" + (j + 1);
} else {
showPath[j] = "无通路";
}
}
minIndex = getAddIndex(savePath, shortestPath);
savePath.add(minIndex);
}
if (savePath.size() > 1) {
while (mark < 6) {// savePath.size()<6 当有不可到达的点是将要出现死循环
int num = savePath.getLast().intValue();
int minIndex = 0;
for (int j = 0; j < path.length; j++) {
if (path[num][j] >= 0) {
if (shortestPath[j] < 0) {
shortestPath[j] = path[num][j] + shortestPath[num];
showPath[j] = showPath[num] + "-->" + (j + 1);
} else {
if (shortestPath[num] + path[num][j] < shortestPath[j]) {
shortestPath[j] = shortestPath[num]
+ path[num][j];
showPath[j] = showPath[num] + "-->" + (j + 1);
}
}
}
}
minIndex = getAddIndex(savePath, shortestPath);
if (minIndex > 0)
savePath.add(minIndex);
mark++;
}
}
return shortestPath;
}
// 获得加入到保存路径的节点
public static int getAddIndex(List list, int num[]) {
int index = 0;
for (int i = 0; i < num.length; i++) {
if (!list.contains(new Integer(i))) {
if (num[i] > 0 && index == 0) {
index = i;
}
if (num[i] > 0 && index > 0) {
if (num[i] < num[index])
index = i;
}
}
}
return index;
}
public static void main(String[] args) {
int path[][] = { { 0, -1, 15, -1, -1, -1 }, { 2, 0, -1, -1, 10, 30 },
{ -1, 4, 0, -1, -1, 10 }, { -1, -1, -1, 0, -1, -1 },
{ -1, -1, -1, 15, 0, -1 }, { -1, -1, -1, 4, 10, 0 } };
int shortestPaht[] = getShortPath(path);
for (int i = 0; i < shortestPaht.length; i++) {
System.out.print("节点 1 到节点 " + (i + 1) + " 的最短距离是"
+ shortestPaht[i] + "\t");
System.out.println("路径为:" + showPath[i]);
}
}
}
使用动态规划来求解每对节点之间的最短路径问题,由于图中的节点是可以转换为矩阵表示法的,所以我们可以通过求解矩阵中每对节点的最短路径来达到求解图中节点最短路径的问题。下面是一个使用动态规划来解决这类问题的一个例子:
package com.sailor.dynamic;
/**
*
* 使用动态规划的方法求取每对节点之间的最短路径
*
* @author sailor
*
*/
public class ShortestPath_Dynamic {
// 求取最短路径
public static String[][] getShortestPath(int data[][]) {
int length = data.length;
String pathShow[][] = new String[length][length];
for (int i = 0; i < data.length; i++)
for (int j = 0; j < data[i].length; j++) {
if (data[i][j] > 0)
pathShow[i][j] = (i + 1) + "-->" + (j + 1);
else
pathShow[i][j] = "不通";
}
int k = 0;
while (k < length) {// 循环将各行加入,即计算将k作为最大通过节点之后的最短路径
for (int i = 0; i < length; i++) {
if (data[k][i] > 0) {// 如果这个节点连通了其他节点,则察看是否将影响到当前的最短路径
for (int m = 0; m < length; m++) {
int temp[] = data[m];
if (temp[k] > 0) {// 如果加入当前节点和加入的节点之间是相通的,执行下面的
if (temp[i] < 0) {
if (i != m) {
temp[i] = temp[k] + data[k][i];
pathShow[m][i] = (m + 1) + "-->" + (k + 1)
+ "-->" + (i + 1);
}
} else {
temp[i] = Math.min(temp[k] + data[k][i],
temp[i]);
pathShow[m][i] = pathShow[m][k] + "-->"
+ (i + 1);
}
}
data[m] = temp;
}
}
}
k++;
}
return pathShow;
}
public static void main(String[] args) {
int data[][] = { { -1, 1, 2, -1, -1, -1 }, { -1, -1, 1, 3, -1, 7 },
{ -1, -1, -1, 1, 2, -1 }, { -1, -1, -1, -1, -1, 3 },
{ -1, -1, -1, -1, -1, 6 }, { -1, -1, -1, -1, -1, -1 } };
String pathShow[][] = getShortestPath(data);
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
if (data[i][j] > 0) {
System.out.print("节点" + (i + 1) + "到节点" + (j + 1)
+ "的最短路径是:" + data[i][j]);
System.out.println(" 路径是" + pathShow[i][j]);
}
}
}
System.out.println("其余没列出的节点之间是不通的");
}
}
- 大小: 13.8 KB
- 大小: 17.5 KB
分享到:
相关推荐
java 最短路径 问题 动态规划java 最短路径 问题 动态规划
用java实现的求迷宫最短路径的算法源代码,代码中有大量注释,容易看懂
JAVA版动态规划解决最短路径问题 啊
用java实现的最短路径问题,里面具体实现了一张图的查询
算法实验,实现了图的单元最短路径的查找,希望有所帮助
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
采用的是分枝定界算法,效率较低
java实现最短路径搜索,并选出最短路径
这个问题通常称为单源最短路径问题. 输入: 第一行为一个整数n,表示包含源在内的顶点的个数,接下来是一个n*n的矩阵,矩阵中-1表示此路不通,否则表示从该顶点到另一顶点的距离。例如对于上图所示的问题我们可以按...
本程序可以应用文件操作,通过读取文件获得输入并且将输出结果以文件形式存在目录文件夹下
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1] 确定终点的...
迪杰斯特拉算法实现K条最短路径! 用java语言进行实现!
有很长时间没有上传了,主要是因为这些天出了些小事。这个是用分支限界法求解单源最短路径问题的算法。
java 具有图形界面的最短路径问题的求解
* (有向)带权图的单源点最短路径算法 */ package dsa; public class BestFSDijkstra extends BestFS { //构造方法 public BestFSDijkstra(Graph g) { super(g); } //更新尚未访问的顶点到源点的最短距离 ...
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权...这个问题通常称为单源最短路径问题。
用java语言和Diskstra算法编写的求最短路径程序。可求得最短路径的长度和路径。
基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的...
单源最短路径问题的java源码 绝对没错误