狄克斯特拉算法案例、局限性及java代码实现

狄克斯特拉算法(Dijkstra )用于计算出不存在非负权重的情况下，起点到各个节点的最短距离文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

可用于解决2类问题：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

• 从A出发是否存在到达B的路径；
• 从A出发到达B的最短路径(时间最少、或者路径最少等)，事实上最后计算完成后，已经得到了A到各个节点的最短路径了；

其思路为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

(2) 更新该节点对应的邻居节点的开销，其含义将稍后介绍。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

(3) 重复这个过程，直到对图中的每个节点都这样做了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

(4) 计算最终路径。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

案例

案例一

先举个简单的例子介绍其实现的思路:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

如下图按Dijkstra算法思路获取起点到终点的最短路径文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

1.首先列出起点到各个节点耗费的时间:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.获取最便宜的节点，由上表知道，起点->B花费最少,计算节点B前往各个邻居节点所需要的时间，并更新原本需要花费更多的时间的节点：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

3.此时B添加进已处理的列表，不再处理了，现在只剩起点->A花费最少，计算节点A前往各个邻居节点所需要的时间，并更新原本需要花费更多的时间的节点：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

4.此时通过倒序可以知道: 起点 -> A -> 终点 ， 该路径即为最短的路径，耗费6分钟文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

案例二

这边以之前的广度优先搜索算法的例子进行举例：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

如上图所示，前边使用广度优先搜索算法可以得知A到H所需要的最少步骤的路径为: A->B->E->H， 本次在各个路径上添加所需花费的时间(当然代表公里数之类的也行)，作为各个路段的权重。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

现在A->B->E->H明显就不再是花费时间最短的路线了，这种添加了权重求最短路径的问题，可以使用狄克斯特拉算法来解决：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

1.获取A到各个节点的耗时，A标志为已处理：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.找出A能到达的最短的节点，计算更新相邻节点的耗时，此时最短的节点为C,C标志为已处理文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.找出A能到达的最短的节点，计算更新相邻节点的耗时，此时最短的节点为B,B标志为已处理文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

3.A相邻节点已处理完，此时找出C能到达的最短的节点，此时为C->D,计算更新相邻节点的耗时，D标志为已处理文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

4.同理更新 F文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

4.同理更新 E文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

5.同理更新 G文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

经过如上步骤后边可以通过倒序得到最短路径为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

A->H的最短路径为:A->C->D->E->H ,总耗时12分钟； 表中其余结果也是最短路径了，比如A->G最短路径: A->C->F->G文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

局限性

该算法不适合负权重的情况，案例三：

这边使用该算法看看为何不适合，计算A->E:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

1.首先起点A出发文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.计算最便宜节点C文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.计算最便宜节点B文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

3.计算最便宜节点D文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

使用 Dijkstra算法计算出来结果将是错误的A->C->D->E，耗费3元，在 狄克斯拉算法中被标志位已处理的节点，便代表中不存在其它到达该节点更便宜的路径了，由于负权重的引入导致了该原则不成立，上述中由于C节点已经被处理过了，结果又需要再次更新C的内容，但对应的此时C后续的子节点比如D可能存在未同步更新的情况，从而导致最终的结果错误。当然也有可能碰巧算对的情况，比如上述案例二中修改A->B = -50的话 ， 可以计算出正确的最短路线为A --> B --> E --> H 耗费-37。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

个人感觉能不能碰巧算对就看是不是负权重再次更新的节点是不是尚未计算相邻节点了，比如案例三B优先于C处理：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

处理B：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

处理C：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

处理D：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

此时正确路径 A->->C->D->E,倒赚98元文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

但是这么做已经和Dijkstra相违背了，在某些情况下可能出现效率极低的现象。所有Dijkstra算法不应该被用于负权重的情况下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

小结

1.广度优先算法BFS主要适用于无权重向图重搜索出步骤最少的路径，当方向图存在权重时，不再适用文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

2.狄克斯特拉算法Dijkstra主要用于有权重的方向图中搜索出最短路径，但不适合于有负权重的情况.对于环图，个人感觉和BFS一样，标志好已处理的节点避免进入死循环，可以支持文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

3.算法的实现主要都是为了避免没有更好的解决办法，而采用穷举法进行解决，当节点数量极大的情况下，算法的优势就会突显出来文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4518.html

java实现

/**
 * 狄克斯特拉算法
 * @author Administrator
 *
 */
public class Dijkstra {
	public static void main(String[] args){
		HashMap<String,Integer> A = new HashMap<String,Integer>(){
			{
				put("B",5);
				put("C",1);
			}
		};
		
		HashMap<String,Integer> B = new HashMap<String,Integer>(){
			{
				put("E",10);
			}
		};
		HashMap<String,Integer> C = new HashMap<String,Integer>(){
			{
				put("D",5);
				put("F",6);
			}
		};
		HashMap<String,Integer> D = new HashMap<String,Integer>(){
			{
				put("E",3);
			}
		};
		HashMap<String,Integer> E = new HashMap<String,Integer>(){
			{
				put("H",3);
			}
		};
		HashMap<String,Integer> F = new HashMap<String,Integer>(){
			{
				put("G",2);
			}
		};
		HashMap<String,Integer> G = new HashMap<String,Integer>(){
			{
				put("H",10);
			}
		};
		HashMap<String,HashMap<String,Integer>> allMap = new HashMap<String,HashMap<String,Integer>>() {
			{
				put("A",A);
				put("B",B);
				put("C",C);
				put("D",D);
				put("E",E);
				put("F",F);
				put("G",G);
			}
		};
		
		
		Dijkstra dijkstra = new Dijkstra();
		dijkstra.handle("A","H",allMap);
	}
	
	private String  getMiniCostKey(HashMap<String,Integer> costs,List<String> hasHandleList) {
		int mini = Integer.MAX_VALUE;
		String miniKey = null;
		for(String key : costs.keySet()) {
			if(!hasHandleList.contains(key)) {
				int cost = costs.get(key);
				if(mini > cost) {
					mini = cost;
					miniKey = key;
				}
			}
		}
		return miniKey;
	}
	
	private void handle(String startKey,String target,HashMap<String,HashMap<String,Integer>> all) {
		//存放到各个节点所需要消耗的时间
		HashMap<String,Integer> costMap = new HashMap<String,Integer>();
		//到各个节点对应的父节点
		HashMap<String,String> parentMap = new HashMap<String,String>();
		//存放已处理过的节点key,已处理过的不重复处理
		List<String> hasHandleList = new ArrayList<String>();
		
		//首先获取开始节点相邻节点信息
		HashMap<String,Integer> start = all.get(startKey);
				
		//添加起点到各个相邻节点所需耗费的时间等信息
		for(String key:start.keySet()) {
			int cost = start.get(key);
			costMap.put(key, cost);
			parentMap.put(key,startKey);
		}
		
		
		//选择最"便宜"的节点，这边即耗费时间最低的
		String minCostKey = getMiniCostKey(costMap,hasHandleList);
		while( minCostKey!=null ) {
			System.out.print("处理节点："+minCostKey);
			HashMap<String,Integer> nodeMap = all.get(minCostKey);
			if (nodeMap!=null) {
				//该节点没有子节点可以处理了，末端节点
				handleNode(minCostKey,nodeMap,costMap,parentMap);
			}
			//添加该节点到已处理结束的列表中
			hasHandleList.add(minCostKey);
			//再次获取下一个最便宜的节点
			minCostKey = getMiniCostKey(costMap,hasHandleList);
		}
		if(parentMap.containsKey(target)) {
			System.out.print("到目标节点"+target+"最低耗费:"+costMap.get(target));
			List<String> pathList = new ArrayList<String>();
			String parentKey = parentMap.get(target);
			while (parentKey!=null) {
				pathList.add(0, parentKey);
				parentKey = parentMap.get(parentKey);
			}
			pathList.add(target);
			String path="";
			for(String key:pathList) {
				path = path + key + " --> ";
			}
			System.out.print("路线为"+path);
		} else {
			System.out.print("不存在到达"+target+"的路径");
		}
	}
	
	private void handleNode(String startKey,HashMap<String,Integer> nodeMap,HashMap<String,Integer> costMap,HashMap<String,String> parentMap) {
	
		for(String key : nodeMap.keySet()) {
			//获取原本到父节点所需要花费的时间
			int hasCost = costMap.get(startKey);
			//获取父节点到子节点所需要花费的时间
			int cost = nodeMap.get(key);
			//计算从最初的起点到该节点所需花费的总时间
			cost = hasCost + cost;
			
			if (!costMap.containsKey(key)) {
				//如果原本并没有计算过其它节点到该节点的花费
				costMap.put(key,cost);
				parentMap.put(key,startKey);
			}else {
				//获取原本耗费的时间
				int oldCost = costMap.get(key);
				if (cost < oldCost) {
					//新方案到该节点耗费的时间更少
					//更新到达该节点的父节点和消费时间对应的散列表
					costMap.put(key,cost);
					parentMap.put(key,startKey);
					System.out.print("更新节点："+key + ",cost:" +oldCost + " --> " + cost);
				}
			}
		}
	}
复制代码

执行完main方法打印信息如下:

    处理节点：C
    处理节点：B
    处理节点：D
    更新节点：E,cost:15 --> 9
    处理节点：F
    处理节点：E
    处理节点：G
    处理节点：H
    到目标节点H最低耗费:12路线为A --> C --> D --> E --> H