python 队列实现的图的BFS,类似于哈夫曼树遍历:
BFS.PNG
栈实现的图的DFS:
DFS.PNG
BFS扩展最短路径:
parent.PNG
Dijkstra(加权最短路径计算):
dijkstra 推导.PNG
dijkstra.PNG 初始化.PNG
Dijkstra.PNG
写了个java版,比起js和python这种基于对象而不是oo语言,有点啰嗦:
import java.util.*;
/**
* @author jajing
*/
public class Dijkstra {
private static class Node implements Comparable<Node>{
String name;
Integer distance;
Node(String name,Integer distance){
this.name = name;
this.distance = distance;
}
@Override
public int compareTo(Node o) {
//正序
return this.distance - o.distance;
}
}
//图的两点间最短路径
public static void main(String[] args) {
Map<String,Map<String,Integer>> map = new HashMap<String,Map<String,Integer>>();
Map mA = new HashMap();mA.put("B",5);mA.put("C",1);
Map mB = new HashMap();mB.put("A",5);mB.put("C",2);mB.put("D",1);
Map mC = new HashMap();mC.put("A",1);mC.put("B",2);mC.put("D",4);mC.put("E",8);
Map mD = new HashMap();mD.put("B",1);mD.put("C",4);mD.put("E",3);mD.put("F",6);
Map mE = new HashMap();mE.put("C",8);mE.put("D",3);
Map mF = new HashMap();mF.put("D",6);
map.put("A",mA);
map.put("B",mB);
map.put("C",mC);
map.put("D",mD);
map.put("E",mE);
map.put("F",mF);
Map<String,Integer> result = dijkstra(map,"A");
for(Map.Entry<String,Integer> e:result.entrySet()){
System.out.println(e.getKey() + ":" + e.getValue());
/**
* A:0
* B:3
* C:1
* D:4
* E:7
* F:10
*/
}
}
public static Map<String,Integer> initDistance(Map<String,Map<String,Integer>> map,String start){
Map<String,Integer> distance = new HashMap<String, Integer>();
for(String key:map.keySet()){
distance.put(key,Integer.MAX_VALUE);
}
return distance;
}
public static Map<String,Integer> dijkstra(Map<String,Map<String,Integer>> map,String start){
//最短距离表,初始都最大化
Map<String,Integer> minDistance = initDistance(map,start);
Set<String> seen = new HashSet<String>();
//最短路径的父结点
Map<String,String> parent = new HashMap<String, String>();
PriorityQueue<Node> pQueue = new PriorityQueue<Node>();
pQueue.offer(new Node(start,0));
parent.put(start,"Null");
minDistance.put(start,0);
while(!pQueue.isEmpty()){
Node current = pQueue.poll();
//一定要在取出时才放到seen去!!
seen.add(start);
String currentName = current.name;
Integer currentDist = current.distance;
Map<String,Integer> connects = map.get(currentName);
for(Map.Entry<String,Integer> entry : connects.entrySet()){
String nextKey = entry.getKey();
Integer nextValue = entry.getValue();
if(seen.contains(nextKey)) continue;
Integer newDistance = currentDist + nextValue;
if(newDistance < minDistance.get(nextKey)){
parent.put(nextKey,currentName);
minDistance.put(nextKey,newDistance);
pQueue.offer(new Node(nextKey,newDistance));
}
}
}
return minDistance;
}
}
这里要感谢@正月点灯笼
的课件
网友评论