给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。
/**
* 迪杰斯特拉算法
* @ graph:图的邻接表
* @ start:起始结点
*/
void Dijkstra(Map<String,List<ENode>> graph, String start){
// 初始化
Map<String,Integer> dis = new HashMap<>();
Map<String,String> path = new HashMap<>();
Map<String,Boolean> mark = new HashMap<>();
String k = start;
for( String id : graph.keySet ){
dis.put( id, Integer.MAX_VALUE );
path.put( id, null );
mark.put( id, false );
}
for( ENode edge : graph.get(start) ){
dis.put( edge.id, edge.w );
path.put( edge.id, start );
}
mark.put( k, true );
int n = graph.keySet().size();// 图中结点个数
// 进行n-2次扫描,每次选一个结点放入S集合
for( int i=1; i<=n-2; i++ ){
k = selectKfromDis(dis,mark);// 从dis中选尚未访问的最小值作为k
mark.put( k, true );
for( ENode edge : graph.get(k) ){
if ( !mark.get(edge.id) && dis.get(k)+edge.w < dis.get(edge.id) ) {
dis.put( edge.id, dis.get(k)+edge.w );
path.put( edge.id, k );
}
}
}
}
/**
* 从dis中选一条尚未访问过的最短的边
*/
String selectKfromDis( Map<String,Integer> dis, Map<String, Boolean> mark ){
int min = Integer.MAX_VALUE;
String id = null;
for( Map.Entry<String,Integer> entry : dis ){
if ( !mark.get(entry.getKey()) && entry.getValue() < min ) {
min = entry.getValue();
id = entry.getKey();
}
}
return id;
}