Часть 2. Как навигационные приложения прокладывают кратчайший путь?
Продолжая тему прошлой статьи, мы поговорим об Алгоритме Дейкстры. Для чего он нужен и какие проблемы он помогает решать.
Все помнят граф, который мы использовали для изображения маршрутов автобуса от точки А до точки B?
Но, предположим, с каждым сегментом (ребром) связывается продолжительность перемещения. И тогда выясняется, что существует более быстрый путь. Так вот, задача, которую мы решали, не совсем бы подошла для ситуации, если у нас есть своя машина, и мы бы хотели добраться от дома до работы на машине.
В конце прошлой части я показал граф. Тот же самый граф, но у него появились веса, а именно длина дорог, по которым мы можем добраться до нашей работы. Давайте, посмотрим на этот граф снова.
Такие графы называются - взвешенные. Терминология взвешенного графа остается такая же. Но их ключевая особенность в том, что в качестве весов мы можем использовать любые значения, будь-то время, затраченное на дорогу от одного узла к другому, или деньги, которые мы потратили, чтобы добраться до точки назначения.
Поиск в ширину, который мы разбирали в предыдущей главе, не умеет работать с взвешенными графами. Он всего лишь ищет кратчайший путь (кратчайшее количество сегментов, ребер, которые мы можем преодолеть, чтобы добраться до конечной точки).
Ниже мы немного изменим наш граф, для более наглядного примера.
Вот, так будет достаточно неплохо, чтобы разобрать на этом графе основные моменты Алгоритма Дейкстры.
Алгоритм Дейкстры состоит из четырех основных шагов:
Найти узел с наименьшей стоимостью (весом);
Обновить стоимость соседей этого узла;
Повторять, пока это не будет сделано для всех узлов графа;
Вычислить итоговый путь.
Давайте попробуем применить этот алгоритм.
Перед началом условимся на том, что вес узлов, к которым мы не можем добраться за 1 ход, будет приравнен к бесконечности.
Создадим небольшую табличку, в которую мы будем заносить данные по мере использования алгоритма. Изначально она будет выглядеть так:
Шаг 1. Найти узел с наименьшей стоимостью. В данном случае самая короткая дорога, по которой мы можем поехать - это дорога от A до D.
Шаг 2. Вычислить, сколько времени потребуется для того, чтобы добраться до всех его соседей.
Стоимость узла E заносится в таблицу, и его родителем назначается узел D. Но также мы обнаружили более короткий маршрут до узла C. До него мы можем добраться с наиболее меньшей стоимостью, поэтому обновим стоимость его и родителя.
Снова шаг 1. Следующий по стоимости - это узел С.
Снова шаг 2. Обновляем значения всех его соседей
Теперь, стоимость узлов E и B обновились. Это означает, что до узла E быстрее дойти через ребро, идущее от узла C. И мы наконец-то нашли первый наш маршрут до точки B.
Теперь его стоимость всего лишь 8. Но на этом работа нашего алгоритма не закончилась. Попробуем повторить шаги.
Снова шаг 1. Следующий по стоимости - это узел E.
Снова шаг 2. Обновляем значения всех его соседей.
Итак, мы нашли более короткий путь до узла B. Стоимость его составит - 6. Если мы будем двигаться через ребро, идущее от узла E.
Смысла продолжать наш алгоритм нет,т.к. узел B является конечным.
Чтобы понять, каким образом выглядит наш кратчайший маршрут, мы можем выстроить цепочку всех родителей, идущих от узла B. То есть наш маршрут будет выглядеть вот так: A - D - C - E - B.
Теперь попробуем написать код такого алгоритма:
const graph = {
'A': {
neighbors: {
'C': 5,
'D': 2
},
parent: null,
cost: null
},
'D': {
neighbors: {
'E': 4,
'C': 2
},
parent: 'A',
cost: 2
},
'C': {
neighbors: {
'E': 1,
'B': 3
},
parent: 'A',
cost: 5
},
'E': {
neighbors: {
'B': 1
},
parent: null,
cost: Infinity
},
'B': {
neighbors: {},
parent: null,
cost: Infinity
}
}
const processed = [];
const find_lowest_cost_node = (graph) => {
let result, value = Infinity
Object.keys(graph).forEach((node) => {
if (!processed.includes(node) && typeof graph[node].cost === 'number') {
if (graph[node].cost < value) {
value = graph[node].cost
result = node
}
}
})
return result
}
const search_quick_way = (graph, endpoint) => {
let way = [endpoint]
while (graph[endpoint].parent) {
way.push(graph[endpoint].parent)
endpoint = graph[endpoint].parent
}
return way.reverse().join(' - ')
}
const search = (graph) => {
let node = find_lowest_cost_node(graph)
while (node) {
let cost = graph[node].cost
let neighbors = graph[node].neighbors
for (let n in neighbors) {
const new_cost = cost + neighbors[n]
if (graph[n].cost > new_cost) {
graph[n].cost = new_cost
graph[n].parent = node
}
}
processed.push(node)
node = find_lowest_cost_node(graph)
}
return graph
}
Вот и все, мы реализовали Алгоритм Дейкстры. Вы можете спросить, а как же навигационные приложение учитывают пробки? Все просто. Если на улице есть пробка, то мы можем увеличивать веса наших ребер. Например добавлять какие-то коэффициенты, которые изменят наши веса, и они станут намного больше, чем другие.
Всем спасибо за внимание!
