Алгоритм Дейкстры добавляет узлы в очередь в том же порядке, что и поиск по ширине (BFS): когда узел проверяется, его непосредственные соседи добавляются в очередь.
Разница в том, как узлы извлекаются из очереди. В то время как BFS делает это в последовательности FIFO (первым пришел - первым вышел), алгоритм Дейкстры делает это по приоритету. Узел с наивысшим приоритетом извлекается из очереди. Приоритет устанавливается стоимостью, которую необходимо получить от источника к этому узлу.
Когда источник A проверяется, его непосредственные соседи добавляются в очередь, поэтому очередь содержит 2 узла:
B (10), C (3)
Для удобства я добавил стоимость к имени каждого узла. Следующий узел, который будет извлечен из очереди и протестирован, - это узел с наивысшим приоритетом = минимальной стоимостью, равной C. После тестирования C очередь выглядит так:
B (7), E (5), D (11)
Стоимость B была обновлена с 10-7, потому что был найден путь с более низкой стоимостью (A -> C -> B). Следующий узел, который должен быть извлечен из очереди - это E. Тестирование E не добавляет ни одного из своих соседей (C, D) в очередь. C уже был протестирован, и D находится в очереди. Очередь после извлечения E выглядит следующим образом:
B (7), D (11)
B, который имеет самый высокий приоритет (самая низкая стоимость из источника) вытащил из очереди. Тестирование B обновляет стоимость D до 7 + 2 = 9. Теперь у нас есть только D в очереди:
D (9)
D вытащено и потому что это цель, поиск прекращается. Найден правильный кратчайший путь стоимостью 9