迪杰斯特拉算法(dijkstra)Java实现及升级 (二)

Edge e12 = new Edge(v2,10);
Edge e14 = new Edge(v4,30);
Edge e15 = new Edge(v5,100);
e1l.add(e14);
e1l.add(e15);
e1l.add(e12);

Edge e23 = new Edge(v3,50);
e2l.add(e23);

Edge e35 = new Edge(v5,10);
e3l.add(e35);

Edge e43 = new Edge(v3,20);
Edge e45 = new Edge(v5,60);
e4l.add(e43);
e4l.add(e45);

/*
以上代码构建有向图
v1---->v5:100
v1----->V4:30
v1------>V2:10

V2------>V3:50
V3------->V5:10
v4------->V3:20
v4------->V5:60
*/
vertexMap.put("v1", v1);
vertexMap.put("v2", v2);
vertexMap.put("v3", v3);
vertexMap.put("v4", v4);
vertexMap.put("v5", v5);

dijkstra("v1","v5");
}

}

算法 的大致说明：

用PriorityQueue来做数据存储。

开始记录了所有的点，及默认的距离。

然后拿出一个点A，再计算其余的点通过点A来到达的距离，选择其中最短的，得到点B。再选择通过点B............最终达到目的。

在网上看到实现不是指定终点的，而是指点起点，便将到其他点的最短路径都罗列出来。

//dijkstra算法实现
public static void dijkstra(String startName){
PriorityQueue pq = new PriorityQueue();//该队列以权值升序排列，因为Vertex实现Comparable接口
Vertex start = vertexMap.get(startName);
start.dist = 0;
for(Vertex v:vertexMap.values())
pq.add(v);
int seenNum = 0;
while(!pq.isEmpty()&&seenNum < vertexMap.size()){
Vertex v = pq.remove();
System.out.println("v0---->"+v.name+":"+v.dist);
if(v.scratch != 0)
continue;
v.scratch = 1;
seenNum++;
for(Edge e:v.adj){
Vertex w = e.dest;
double v_to_w = e.cost;
if(w.dist > v.dist + v_to_w){
w.dist = v.dist + v_to_w;
w.prev = v;
pq.remove(w);//出队
pq.add(w);//按优先级插在队头，先插入的在队头，依次往后

}
}
}
System.out.println("hello !");
while(pq.peek() != null ){
System.out.println(pq.poll());
}
}