Алгоритм (4): Графический алгоритм Дейкстры

Введение в алгоритмы

Алгоритм Дейкстры используется для вычисления кратчайшего расстояния от начальной точки до каждого узла при отсутствии неотрицательных весов.

Может использоваться для решения 2-х типов задач:

Есть ли путь из А в Б;
Кратчайший путь из А в В (наименьшее время, или наименьший путь и т. д.), по сути, после окончательного расчета получен кратчайший путь из А в каждый узел;

Идея такова:

(1) Найдите самый «дешевый» узел, до которого можно добраться за кратчайшее время.

(2) Обновить стоимость соседнего узла, соответствующего этому узлу, смысл которого будет представлен позже.

(3) Повторяйте этот процесс, пока не сделаете это для каждого узла графа.

(4) Рассчитать конечный путь.

кейс

Дело номер один

Давайте возьмем простой пример, чтобы представить идею его реализации:

Как показано на рисунке ниже, кратчайший путь от начальной точки до конечной точки получается по идее алгоритма Дейкстры.

1. Сначала укажите время от начальной точки до каждого узла:

родительский узел	узел	кропотливый
отправная точка	A	6 минут
отправная точка	B	2 минуты
..	конец	∞ как бесконечность

2. Получите самый дешевый узел.Из приведенной выше таблицы начальная точка -> B стоит меньше всего, рассчитайте время, необходимое узлу B, чтобы перейти к каждому соседнему узлу, и обновите узел, который изначально занимал больше времени:

родительский узел	узел	кропотливый
B	A	5 минут Время обновления, первоначально 6 минут
отправная точка	B	2 минуты
B	конец	7 минут на обновление

3. В это время B добавляется в обработанный список и больше не обрабатывается.Теперь только начальная точка -> A тратит меньше всего, вычислить время, необходимое узлу A для перехода к каждому соседнему узлу, и обновить узел, который изначально заняло больше времени:

родительский узел	узел	кропотливый
-	A	5 минут Время обновления, первоначально 6 минут
отправная точка	B	2 минуты
A	конец	6 минут Время обновления, первоначально 7 минут

4. В это время вы можете узнать в обратном порядке: Начальная точка -> А -> конечная точка, этот путь является кратчайшим путем, который занимает 6 минут.

Случай 2

здесь раньшеАлгоритм поиска в ширинуПример например:

Как показано на рисунке выше, алгоритм поиска в ширину, используемый на переднем плане, может знать, что путь с наименьшими требуемыми шагами от A до H: A->B->E->H, На этот раз добавьте время, затрачиваемое на каждый путь (конечно, оно также представляет собой количество километров), как вес каждого сегмента дороги.

Теперь A->B->E->H, очевидно, больше не является кратчайшим путем.Эта проблема добавления весов для нахождения кратчайшего пути может быть решена с помощью алгоритма Дейкстры:

1. Получите время, затраченное от A до каждого узла, и A помечен как обработанный:

родительский узел	узел	кропотливый
A	B	5 минут
A	C	1 минута
..	H	∞ как бесконечность

2. Найдите кратчайший узел, которого может достичь А, и рассчитайте время, затрачиваемое на обновление соседних узлов.На данный момент кратчайшим узлом является С, а С помечен как обработанный.

родительский узел	узел	кропотливый	логотип
A	B	5 минут
A	C	1 минута	C был обработан
C	D	6 минут
C	F	7 минут
..	H	∞ как бесконечность

2. Найдите кратчайший узел, которого может достичь А, и рассчитайте время, необходимое для обновления соседних узлов.В это время кратчайшим узлом является В, а В помечен как обработанный.

родительский узел	узел	кропотливый	логотип
A	B	5 минут	Б был обработан
A	C	1 минута	C был обработан
C	D	6 минут
C	F	7 минут
B	E	15 минут
..	H	∞ как бесконечность

3. Обработан соседний узел A. В это время найдите кратчайший узел, которого может достичь C. На данный момент это C-> D. Подсчитайте время, затрачиваемое на обновление соседнего узла, и D отмечен как обработано.

родительский узел	узел	кропотливый	логотип
A	B	5 минут	Б был обработан
A	C	1 минута	C был обработан
C	D	6 минут	D был обработан
C	F	7 минут
D	E	9 минут
..	H	∞ как бесконечность

4. Аналогично обновить F

родительский узел	узел	кропотливый	логотип
A	B	5 минут	Б был обработан
A	C	1 минута	C был обработан
C	D	6 минут	D был обработан
C	F	7 минут	F обработано
D	E	9 минут
F	G	9 минут
..	H	∞ как бесконечность

4. Аналогично обновить E

родительский узел	узел	кропотливый	логотип
A	B	5 минут	Б был обработан
A	C	1 минута	C был обработан
C	D	6 минут	D был обработан
C	F	7 минут	F обработано
D	E	9 минут	E обработано
F	G	9 минут
E	H	12 минут

5. Аналогично обновить G

родительский узел	узел	кропотливый	логотип
A	B	5 минут	Б был обработан
A	C	1 минута	C был обработан
C	D	6 минут	D был обработан
C	F	7 минут	F обработано
D	E	9 минут	E обработано
F	G	9 минут	G был обработан, G->H не снижает стоимость, поэтому требуется время, чтобы не обновлять H
E	H	12 минут

После вышеуказанных шагов кратчайший путь можно получить в обратном порядке:

Кратчайший путь A->H: A->C->D->E->H, что в сумме занимает 12 минут; Остальные результаты в таблице также являются кратчайшими путями, такими как кратчайшие пути A->G: A->C->F->G

ограничение

Этот алгоритм не подходит для случая отрицательных весов, случай 3:

Используйте приведенный здесь алгоритм, чтобы понять, почему он не подходит, и рассчитайте A->E:

1. Первый старт из начальной точки А

родительский узел	узел	кропотливый
A	B	100 юаней
A	C	1 юань
..	конец	∞ как бесконечность

2. Рассчитайте самый дешевый узел C

родительский узел	узел	кропотливый	логотип
A	B	100 юаней
A	C	1 юань	C был обработан
C	D	2 юаня
..	конец	∞ как бесконечность

2. Рассчитайте самый дешевый узел B

родительский узел	узел	кропотливый	логотип
A	B	100 юаней	Б был обработан
B	C	-100 юаней	C был обработан, но C все еще нуждается в обновлении здесь
C	D	2 юаня
..	конец	∞ как бесконечность

3. Рассчитайте самый дешевый узел D

родительский узел	узел	кропотливый	логотип
A	B	100 юаней	Б был обработан
B	C	-100 юаней	C был обработан, но C все еще нуждается в обновлении здесь
C	D	2 юаня	D был обработан
D	E	3 юаня

Использование алгоритма Дейкстры для вычисления результата будет ошибочным A->C->D->E стоимостью 3 юаня в Узел, который был обработан битом флага в алгоритме Dixra, означает, что нет другого более дешевого пути к узлу.Из-за введения отрицательных весов этот принцип не выполняется.В вышеприведенном примере был обработан узел C ., в результате содержимое C необходимо обновить снова, но, соответственно, последующие дочерние узлы C, такие как D, могут не обновляться синхронно в это время, что приводит к ошибке в конечном результате. Конечно, также возможно, что расчет окажется правильным.Например, в приведенном выше случае 2, если изменить A->B = -50, правильный кратчайший маршрут может быть рассчитан как A --> B -- > E --> H стоимость -37.

Лично я считаю, что может ли это быть правильным, зависит от того, не вычислил ли еще узел, отрицательный вес которого снова обновляется, соседние узлы.Например, в случае 3 B имеет приоритет над C:

Процесс Б:

родительский узел	узел	кропотливый	логотип
A	B	100 юаней	Б был обработан
A	C	-100 юаней
..	конец	∞ как бесконечность

Процесс С:

родительский узел	узел	кропотливый	логотип
A	B	100 юаней	Б был обработан
A	C	-100 юаней	C был обработан
C	D	-99 юаней
..	конец	∞ как бесконечность

Процесс Д:

родительский узел	узел	кропотливый	логотип
A	B	100 юаней	Б был обработан
A	C	-100 юаней	C был обработан
C	D	-99 юаней	D был обработан
D	E	-98 юаней

На этот раз правильный путь A->->C->D->E принесет 98 юаней.

Но это противоречит Дейкстре и в некоторых случаях может быть крайне неэффективным. Все алгоритмы Дейкстры не следует использовать в случае отрицательных весов.

резюме

1. Алгоритм BFS в ширину в основном подходит для повторного поиска пути с наименьшим количеством шагов в невесомом графе направлений, когда граф направлений имеет веса, он уже не применим.

2. Алгоритм Дейкстры в основном используется для поиска кратчайшего пути во взвешенных направленных графах, но он не подходит для случаев с отрицательными весами.Для кольцевых графов мое личное ощущение такое же, как BFS, помечая обрабатываемые узлы, чтобы избежать ввода бесконечный цикл, может поддерживать

3. Реализация алгоритма в основном предназначена для того, чтобы избежать отсутствия лучшего решения, и для его решения используется исчерпывающий метод.Когда количество узлов чрезвычайно велико, будут выделены преимущества алгоритма.

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

Публичный аккаунт WeChat: