Алгоритм Дейкстры — это простой метод поиска минимального пути через граф с ребрами и весами.
задача: вам будет дан граф с весом для каждого ребра, исходной вершины, и вам нужно найти минимальное расстояние от исходной вершины до остальных вершин.
Примечание. В этом блоге объясняется алгоритм, а также рассказывается, как реализовать алгоритм на любом языке. Этот блог предполагает, что у вас есть представление о графиках.
предположим, что у нас есть указанный выше неориентированный граф, а источник равен 1. Наша цель - найти кратчайший путь от исходной вершины до каждой другой вершины, т. Е. Путь с меньшей стоимостью (сумма всех весов ребер в пути). Например, одним из возможных путей от 1 до 5 будет 3 (2+1).
Как это работает
во-первых, предположим, что расстояние от исходной вершины до любой другой вершины равно бесконечности.
вершины = [1,2,3,4,5]
расстояния = [0,inf,inf,inf,inf]
выберите вершину
сравните расстояние от источника до вершины с текущим расстоянием до вершины, если оно больше текущего расстояния, оставьте, в противном случае обновите расстояние.
Затем соседняя вершина как посещенная
После того, как все соседние вершины будут завершены, выберите вершину из посещенных с меньшим расстоянием и повторите процесс для всех вершин.
После того, как вершины завершены, вы получите вывод минимального расстояния от исходной вершины до всех других вершин, если путь существует.
Временная сложность
Алгоритм кратчайшего пути Дейкстры равен O(E log V), где:
E- количество ребер
V- количество вершин
Пространственная сложность:O(|V|)
вы можете найти реализацию алгоритма Дейкстры в моем github.
