迪科斯彻(Dijkstra)算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。
在一个有向非负权重的图中，可以知道如AC>AB,这AC+CB>AB，这一不等式有点贪心算法的思想，每次选择时都做出贪心选择。在迪科斯彻算法中就是使用了上面的原理进行求解的。具体的介绍可以wiki一下：http://zh.wikipedia.org/wiki/Dijkstra算法.里面已经包含了伪代码。下面是Java版的实现代码，需要注意的是这里没有使用伪代码中的优先队列，而是使用一个布尔类型的标记数组来通过标记来模拟优先队列的"出队列"。
package com.wly.algorithmbase.search;
/**
* 迪科斯彻算法
* 基于广度优先搜索，使用优先队列存储检索信息
* 伪代码：
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 初始化
3 d[v] := infinity // 各 的已知最短距 先 成 大
4 previous[v] := undefined // 各点的已知最短路径上的前趋都未知
// 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijkstra演算法主
9 u := Extract_Min(Q)
10 S.append(u)
11 for each edge outgoing from u as (u,v)
12 if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
13 d[v] := d[u] + w(u,v)// 更新路径长度到更小的那个和值。
14 previous[v] := u // 前
* @author wly
*
*/
public class DijstraAlgorithm {
private static int IMAX = 10000; //不连通状态
public static int[][] adjMat = {
{0,10,3,IMAX},
{IMAX,0,4,5},
{IMAX,4,0,10},
{IMAX,IMAX,IMAX,0}
};
public static void main(String[] args) {
DijstraAlgorithm dijstraAlgorithm = new DijstraAlgorithm();
int start = 2;
int end = 3;
System.out.println("------测试------");
System.out.println("\n从" + start + "到" + end
+ "的距离是:" + dijstraAlgorithm.reslove(adjMat, start, end));
System.out.println("------测试------");
start = 0;
end = 3;
System.out.println("\n从" + start + "到" + end
+ "的距离是:" + dijstraAlgorithm.reslove(adjMat, start, end));
}
/**
* 在用邻接矩阵adjMat表示的图中，求解从点s到点t的最短路径
* @param adjMat 邻接矩阵
* @param s 起点
* @param t 终点
* @return
*/
public int reslove(int[][] adjMat,int s,int t) {
//判断参数是否正确
if(s < 0 || t < 0 || s >=adjMat.length || t >= adjMat.length) {
System.out.println("错误，顶点不在图中!");
return IMAX;
}
//用来记录某个顶点是否已经完成遍历，即替代优先队列的"移出队列"动作
boolean[] isVisited = new boolean[adjMat.length];
//用于存储从s到各个点之间的最短路径长度
int[] d = new int[adjMat.length];
//初始化数据
for(int i=0;i
0 && index != t) {
int min = IMAX;
for(int i=0;i
d[i] && !isVisited[i]) { min = d[i]; index = i; } } if(index == t || unVisitedNum == 0) { System.out.print(index); //打印最短路径 } else { System.out.print(index + "=>"); //打印最短路径 } for(int i=0;i
运行效果：
------测试------
2=>1=>3
从2到3的距离是:9
------测试------
0=>2=>1=>3
从0到3的距离是:12
对应的图结构：
O啦~~~
装载请保留出处:http://blog.csdn.net/u011638883/article/details/17200869
谢谢!!