贪心算法(五)——迪杰斯特拉算法
问题描述
给一个有向无环带权图，并给一个起点，求出该原点到所有顶点的最短路径。
数据结构
- dis： Map<String,Integer> dis; 存储原点s到指定节点的最短路径长度。 key表示节点编号，value表示s到该终止节点的最短路径长度。
- path： Map<String,String> path; 存储以指定结点为终点的最短路径中，该终点的上一个结点的编号。 key表示终点编号，value表示终点的前驱结点编号。
- S集合 和 V集合
将所有的结点分成两个集合：
- S集合中存储已经计算出最短路径的结点；
- V集合中存储尚未计算出最短路径的结点。
- k结点： 最新选入S集合的结点，即刚刚计算出最短路径的结点。
- mark： Map<String,Boolean> mark; 用于标识指定结点是否已被选入S集合（即是否已经计算出最短路径）。 key为结点编号，value为是否属于S集合。
算法步骤
- 初始化 a）初始化mark：将初始节点s选入S集合； b）初始化dis：将与s结点所有出边的权值写入dis中； c）初始化path：将所有与s结点直接关联的终止结点的path值设为s；
- 遍历dis，找出最短的边，将该边的终点设为k，并纳入S集合中；
- 遍历k的所有出边，并更新dis和path（设与k直接关联的所有结点为j）： 若d[k]+w< k,j> 小于 d[j]，则： a）d[j]=d[k]+w< k,j> b）path[j]=k;
- 重复步骤2、3，n-2次后停止。（n为结点数量）
示例
代码实现
/**
* 迪杰斯特拉算法
* @ 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;
}举报
腾讯云开发者
