图的遍历算法(1):Dijkstra
伪代码描述
时间复杂度分析
Priority Queues:
1.Linked list: O(n2)
2.Binary Heap:O((m+n)log n)
步骤分析
代码
//use for get weight///
public double getEdge( int node1, int node2 ){
double w ;
w = weights.get(node1).get(node2);
return w;
}
public double shortestDistance(int s, int t){
int u;
double k;
double[] dist = new double[nodeSet.size()];
int[] prev = new int[nodeSet.size()];
dist[s] = 0;
prev[s] = -1;
visited.put(s, true);
PriorityQueue p = new PriorityQueue<>();
p.add(0.0);
for (Integer i: nodeSet){
if(i!=s){
dist[i]=9999.0;//represent infinite
prev[i]=-1;//represent null
p.add(9999.0);
visited.put(i, false);
}
}
while(!p.isEmpty()){
k = (double) p.poll();//k is the smallest one
for(u=0;u<dist.length;u++){
if(dist[u]==k){
break;
}
}//find node u
visited.put(u, true);
for (Integer v: nodeSet){
List<Integer> list = data.get((Integer)u);
if(list.contains((Integer)v)&&visited.get(v)==false){
if(dist[u]+getEdge(u, v)<dist[v]){
p.remove(dist[v]);
dist[v]=(int) (dist[u]+getEdge(u, v));
p.add(dist[v]);
prev[v]=u;
}
}
}
}
// System.out.println(visited.toString());
// System.out.println(Arrays.toString(prev));
// System.out.println(Arrays.toString(dist));
// System.out.println(p.toString());
//for testing
return dist[t];
}
运行结果
public static void main(String[] args) {
Digraph g = new Digraph();
g.add(0);
g.add(1);
g.add(2);
g.add(3);
g.add(4);
g.add(5);
g.add(6);
g.addEdge(0,1,14);
g.addEdge(0,3,22);
g.addEdge(0,4,4);
g.addEdge(2,1,16);
g.addEdge(2,3,12);
g.addEdge(4,3,12);
g.addEdge(1,6,3);
g.addEdge(4,5,10);
g.addEdge(6,5,1);
System.out.println(g.shortestDistance(0, 4));
}