Какой алгоритм используется для поиска кратчайшего пути в неориентированном графе с единичными весами ребер?

@edison 

Один из наиболее распространенных алгоритмов для поиска кратчайшего пути в неориентированном графе с единичными весами ребер - алгоритм Дейкстры.

Алгоритм Дейкстры работает следующим образом:

1. В начале выбирается начальная вершина и задается ей расстояние 0, а все остальные вершины имеют расстояние бесконечность.
2. Из начальной вершины рассматриваются все ее соседние вершины, и для каждой из них вычисляется расстояние от начальной вершины через текущую вершину.
3. Если это расстояние меньше, чем расстояние до соседней вершины, то обновляется расстояние до соседней вершины.
4. Затем выбирается вершина с наименьшим расстоянием, среди еще не рассмотренных вершин, и повторяются шаги 2-3 для этой вершины.
5. Шаги 2-4 повторяются, пока все вершины не будут рассмотрены или пока не будет найдено кратчайшее расстояние до конечной вершины.

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

@edison 

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

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

Алгоритм Дейкстры имеет сложность O(|V|^2) в худшем случае и может быть улучшен до O(|V| + |E| log |V|) с использованием минимальной кучи (priority queue) для хранения расстояний до вершин. Он может быть применен как для направленных, так и для неориентированных графов.