Какие знаешь алгоритмы поиска кратчайшего пути

В Java популярны алгоритмы поиска кратчайшего пути: 1. **Дейкстры** — для графов с неотрицательными весами. Использует приоритетную очередь. ```java PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance)); ``` 2. **A*** — оптимизированный Дейкстры с эвристикой (например, манхэттенское расстояние). 3. **Bellman-Ford** — работает с отрицательными весами, но медленнее (O(VE)). 4. **Floyd-Warshall** — для всех пар вершин (O(V³)), работает с отрицательными весами (но не с циклами). 5. **BFS** — для невзвешенных графов (кратчайший путь = минимальное количество ребер). Пример Дейкстры: ```java while (!pq.isEmpty()) { Node current = pq.poll(); for (Edge edge : current.edges) { int newDist = current.distance + edge.weight; if (newDist < edge.target.distance) { edge.target.distance = newDist; pq.add(edge.target); } } } ```