Java解最短路径问题

在求解单源路径问题时存在一个简单的算法，这个算法通称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("其余没列出的节点之间是不通的");
	}
}

 

评论

10 楼 nange223 2011-09-20  

你的二维数组的数据"int data[][]"是依据什么构造？

9 楼 zpsailor 2010-05-11  

justlive 写道

好可怕，建议整理一下。看着太晕了

空了整理

8 楼 justlive 2010-05-11  

好可怕，建议整理一下。看着太晕了

7 楼 zpsailor 2010-05-11  

szgaea 写道

hadoop有个计算最短路径的算法,俺觉得不错

说来学习学习呀

6 楼 szgaea 2010-05-11  

hadoop有个计算最短路径的算法,俺觉得不错

5 楼 zpsailor 2010-05-10  

lyhngu 写道

太过程化..

是啊 因为是实验课上做的 呵呵

4 楼 pouyang 2010-05-10  

我记得大学的时候，如果两个点上有多个最短路径，也只能取出一条路径，现在的一半公交地铁路线查询貌似也是这样，如果有多条最短路径也只显示出一条。

3 楼 lyhngu 2010-05-10  

太过程化..

2 楼 zpsailor 2010-05-10  

cectsky 写道

+1            

？

1 楼 cectsky 2010-05-10  

+1