友情提示：转载请注明出处【作者 idlear 博客：http://blog.****.net/idlear/article/details/19687579】
Dijkstra算法是解决带权重有向图上的单源最短路径问题，必须路径值都为正数。如果实现方式合适的话，他的运行时间要低于我们之前介绍的Bellman-Ford算法的运行时间。如果介绍Dijkstra算法的过程你会发现他其实跟我们直接介绍的prim算法非常的相似。他们都是维护一个最小优先队列，最小优先队列维护的值还是key，开始节点到当前节点的最短距离估计。我们不断的从最小优先队列里取节点，加入到我们集合s中，知道最小优先队列为空，则开始节点到所有节点的最短路径就被我们计算出来了，跟prim算法是一样的，也是运用了贪心算法。我们来看一下例图：
public class Dijkstra {
private int max=10000;
public void Dijkstra(int[][]map,int start,int end){
ArrayList list =new ArrayList();
for (int i = 0; i < map.length; i++) {
if (i==start) {
list.add(new Node(i,0,null));
}else{
list.add(new Node(i,max,null));
}
}
while (!list.isEmpty()) {
Collections.sort(list);
Node n=(Node) list.remove(1);
for (int i = 0; i < map.length; i++) {
if (map[n.getId()][i]==0) {
continue;
}
for (Object object : list) {
Node e=(Node) object;
relex(n,e,map[n.getId()][i]);
}
}
}
}
public void relex(Node s,Node e,int length){
if (e.getKey()>s.getKey()+length) {
e.setKey(s.getKey()+length);
e.setP(s);
}
}
}
class Node implements Comparable<Node>{
private int id;
private int key;
private Node p;
@Override
public int compareTo(Node o) {
if(this.getKey()>o.getKey()){
return -1;
}
return 1;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public Node getP() {
return p;
}
public void setP(Node p) {
this.p = p;
}
public Node(int id, int key, Node p) {
super();
this.id = id;
this.key = key;
this.p = p;
}
}