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

Алгоритмы поиска кратчайшего пути

Кратчайший путь (shortest path) — это путь между двумя вершинами графа с минимальной суммой весов рёбер. Это классическая задача в информатике с множеством практических применений: GPS навигация, сетевая маршрутизация, социальные сети.

1. Dijkstra (Дейкстра)

Один из самых популярных алгоритмов для взвешенных графов с неотрицательными весами.

Идея: от стартовой вершины постепенно расслабляем расстояния до всех остальных вершин, всегда выбирая вершину с минимальным известным расстоянием.

import java.util.*;

public class Dijkstra {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    public static int[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[0], b[0]) // сортируем по расстоянию
        );
        pq.offer(new int[]{0, start}); // {расстояние, вершина}
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0], u = current[1];
            
            // Если уже обработали эту вершину с меньшим расстоянием
            if (d > dist[u]) continue;
            
            // Проверяем соседей
            for (Edge edge : graph.get(u)) {
                int v = edge.to;
                int newDist = dist[u] + edge.weight;
                
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.offer(new int[]{newDist, v});
                }
            }
        }
        
        return dist;
    }
    
    public static void main(String[] args) {
        // Граф: вершины 0-5
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < 6; i++) graph.add(new ArrayList<>());
        
        // Добавляем рёбра: вершина, вес
        graph.get(0).add(new Edge(1, 4));
        graph.get(0).add(new Edge(2, 2));
        graph.get(1).add(new Edge(2, 1));
        graph.get(1).add(new Edge(3, 5));
        graph.get(2).add(new Edge(3, 8));
        graph.get(2).add(new Edge(4, 10));
        graph.get(3).add(new Edge(4, 2));
        graph.get(4).add(new Edge(5, 3));
        
        int[] distances = dijkstra(graph, 0);
        
        for (int i = 0; i < distances.length; i++) {
            System.out.println("До вершины " + i + ": " + distances[i]);
        }
    }
}

Сложность: O((V + E) log V) с приоритетной очередью

Плюсы: эффективен, гарантирует оптимальное решение

Минусы: не работает с отрицательными весами

2. Bellman-Ford (Беллман-Форд)

Работает с отрицательными весами и может обнаружить циклы отрицательного веса.

public class BellmanFord {
    static class Edge {
        int from, to, weight;
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    
    public static int[] bellmanFord(int n, List<Edge> edges, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // Релаксируем рёбра n-1 раз
        for (int i = 0; i < n - 1; i++) {
            for (Edge edge : edges) {
                if (dist[edge.from] != Integer.MAX_VALUE &&
                    dist[edge.from] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }
        
        // Проверка цикла отрицательного веса
        for (Edge edge : edges) {
            if (dist[edge.from] != Integer.MAX_VALUE &&
                dist[edge.from] + edge.weight < dist[edge.to]) {
                System.out.println("Найден цикл отрицательного веса!");
                return null;
            }
        }
        
        return dist;
    }
}

Сложность: O(V × E)

Плюсы: работает с отрицательными весами, обнаруживает циклы

Минусы: медленнее Dijkstra

3. A* (A-star)

Оптимизация Dijkstra с использованием эвристической функции (heuristic).

public class AStar {
    static class Node {
        int id, gCost, hCost;
        Node parent;
        
        int getFCost() {
            return gCost + hCost; // f = g + h
        }
    }
    
    // Простая эвристика: манхеттенское расстояние
    static int heuristic(int current, int goal) {
        // Предположим, вершины с номерами близки к координатам
        return Math.abs(current - goal);
    }
    
    public static List<Integer> aStar(List<List<int[]>> graph, int start, int goal) {
        PriorityQueue<Node> openSet = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.getFCost(), b.getFCost())
        );
        
        Map<Integer, Node> nodes = new HashMap<>();
        Node startNode = new Node();
        startNode.id = start;
        startNode.gCost = 0;
        startNode.hCost = heuristic(start, goal);
        nodes.put(start, startNode);
        openSet.offer(startNode);
        
        Set<Integer> closedSet = new HashSet<>();
        
        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            
            if (current.id == goal) {
                // Восстанавливаем путь
                List<Integer> path = new ArrayList<>();
                Node node = current;
                while (node != null) {
                    path.add(0, node.id);
                    node = node.parent;
                }
                return path;
            }
            
            closedSet.add(current.id);
            
            // Проверяем соседей
            for (int[] neighbor : graph.get(current.id)) {
                int nextId = neighbor[0];
                int weight = neighbor[1];
                
                if (closedSet.contains(nextId)) continue;
                
                int newGCost = current.gCost + weight;
                
                Node nextNode = nodes.get(nextId);
                if (nextNode == null || newGCost < nextNode.gCost) {
                    nextNode = new Node();
                    nextNode.id = nextId;
                    nextNode.gCost = newGCost;
                    nextNode.hCost = heuristic(nextId, goal);
                    nextNode.parent = current;
                    nodes.put(nextId, nextNode);
                    openSet.offer(nextNode);
                }
            }
        }
        
        return new ArrayList<>(); // пути нет
    }
}

Сложность: O((V + E) log V) в лучшем случае

Плюсы: быстрее Dijkstra с хорошей эвристикой

Минусы: требует определения эвристической функции

4. BFS (поиск в ширину)

Для невзвешенных графов или графов с равными весами.

public class BFS {
    public static int[] bfs(List<List<Integer>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            
            for (int v : graph.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
        
        return dist;
    }
}

Сложность: O(V + E)

Плюсы: просто, быстро для невзвешенных графов

Минусы: работает только для невзвешенных графов

5. Floyd-Warshall (Флойд-Уоршелл)

Находит кратчайшие пути между всеми парами вершин.

public class FloydWarshall {
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        
        // Копируем исходный граф
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // Основной алгоритм
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE &&
                        dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], 
                            dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        return dist;
    }
}

Сложность: O(V³)

Плюсы: находит пути между всеми вершинами

Минусы: медленнее для больших графов

6. DFS (поиск в глубину)

Для простых графов, может найти путь (но не обязательно кратчайший).

public class DFS {
    static boolean dfs(List<List<Integer>> graph, int current, int goal,
                       Set<Integer> visited, List<Integer> path) {
        if (current == goal) {
            path.add(current);
            return true;
        }
        
        visited.add(current);
        path.add(current);
        
        for (int next : graph.get(current)) {
            if (!visited.contains(next)) {
                if (dfs(graph, next, goal, visited, path)) {
                    return true;
                }
            }
        }
        
        path.remove(path.size() - 1);
        return false;
    }
}

Сравнение алгоритмов

Практический пример: навигация в городе

public class Navigation {
    public static void main(String[] args) {
        // Граф: перекрёстки и дороги
        List<List<int[]>> cityMap = new ArrayList<>();
        // ...
        
        // Используем Dijkstra для GPS навигации
        int[] distances = dijkstra(cityMap, 0); // от перекрёстка 0
        
        // Выводим маршрут
        for (int i = 0; i < distances.length; i++) {
            System.out.println("До перекрёстка " + i + ": " + distances[i] + " км");
        }
    }
}

Выбор алгоритма зависит от структуры графа, наличия отрицательных весов и требуемой производительности.