Задача о кратчайшем пути — алгоритм Дейкстры

Отсканируйте QR-код ниже или WeChat, чтобы найти официальную учетную запись.菜鸟飞呀飞, вы можете следить за публичной учетной записью WeChat, читать дальшеSpring源码分析,Java并发编程,Netty源码系列а такжеMySQL工作原理статья.

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

Некоторое время назад я видел статью, в которой упоминалась десятка лучших алгоритмов, правящих миром, одним из которых является алгоритм Дейкстры, который в основном решает проблему «кратчайшего пути». Хотя это утверждение немного преувеличено, оно действительно широко используется в реальной жизни, например, в картографическом программном обеспечении и т. Д., Большинство игр имеют автоматический поиск пути и другие функции.Используемый алгоритм поиска A * также оптимизирован на основе алгоритма Дейкстры. . Так как же реализован алгоритм Дейкстры?

Если теперь у нас есть следующий ориентированный граф, в графе есть 6 вершин, пронумерованных от 1 до 6, прямая линия со стрелками означает, что одна вершина может достигать другой вершины, а числа на прямой линии представляют два расстояния между вершинами. , теперь найдите кратчайшее расстояние от вершины 1 до вершины 6.

Так как точек на графике относительно немного, то мы можем вычислить этот результат непосредственно ручным расчетом, но если вершин много, их тысячи, вручную посчитать сложно, мы можем посчитать только через программу, то наш программа Как это написать?

идеи

Из рисунка видно, что вершина 1 может напрямую добраться только до вершин 2, 3 и 5, но не может напрямую добраться до вершины 6, поэтому, чтобы добраться до 6 из 1, ее нужно перенести из других вершин.

Мы определяем массив для представления расстояния от каждой вершины до вершины 1, индекс массива представляет номер вершины, а значение элемента массива представляет минимальное расстояние до вершины 1.

1. В начале мы находимся на вершине 1, вершина 1 может достигать 2, 3, 5, состояние массива следующее.

   показатель	1	2	3	4	5	6
   кратчайшее расстояние	0	60	10	null	50	null

2. При переходе от вершины 2 вершина 2 может достичь вершины 4, а расстояние равно 35, поэтому расстояние от вершины 1 до вершины 4 равно 60+35=95, а состояние массива следующее:

показатель	1	2	3	4	5	6
кратчайшее расстояние	0	60	10	95	50	null

3. Транзит из вершины 3, вершина 3 может достичь вершины 4 на расстоянии 30. Если вы проходите через вершину 3, то расстояние от 1 до 4 равно 40, что меньше расстояния через 2, поэтому расстояние от вершины 4 в массиве обновляется до 40. Вершина 3 также может достигать вершины 5. Аналогично, через вершину 2 расстояние от 1 до 5 равно 10+25=35, что меньше, чем расстояние от 1 до непосредственного достижения 5. Следовательно, расстояние до вершины 5 в массиве обновляется до 35. После обновления состояние массива следующее:

показатель	1	2	3	4	5	6
кратчайшее расстояние	0	60	10	40	35	null

4. Перенос из вершины 5, вершина 5 может достигать 2, если вершина 1 достигает 2 через вершину 5, расстояние составляет 35 + 30 = 65, что больше, чем вершина 1, и непосредственно достигает 2, поэтому оно не обновляется. Поскольку вершина 2 уже прошла все точки, которых она может достичь, ее не нужно проходить позже. Вершина 5 также может достигать вершины 6, поэтому расстояние от 1 до 6 равно 35+105=140, а состояние массива следующее:

показатель	1	2	3	4	5	6
кратчайшее расстояние	0	60	10	40	35	140

5. Из вершины 4 вершина 4 также может достичь вершины 6. Если пройти через вершину 4, то расстояние от 1 до 6 будет 40+15=55, что меньше, чем при переходе из 5, поэтому обновите массив, после обновления состояние массива будет следующим:

показатель	1	2	3	4	5	6
кратчайшее расстояние	0	60	10	40	35	55

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

Код

Во-первых, нам нужно представить этот ориентированный граф в коде.Обычно существует два способа представления графа: первый — это матрица смежности (то есть двумерный массив), а второй — список смежности (то есть, массив + связанный список), Здесь мы выбираем метод списка смежности для представления ориентированного графа.

Кроме того, нам также необходимо определить ребра между вершинами.Ребро имеет начальную точку и конечную точку, а также информацию о весе ребра, то есть длину, которая представлена ​​классом Edge. код показывает, как показано ниже:

private class Edge {
    // 起始定点
    public int s;
    // 终止定点
    public int t;
    // 边的权重
    public int weight;

    Edge(int s, int t, int weight) {
        this.s = s;
        this.t = t;
        this.weight = weight;
    }
}

Ориентированный граф представлен классом Graph.В классе есть два свойства: количество вершин v и массив adj информации, описывающей ребра между вершинами.Мы также предоставляем метод: addEdge, который используется для добавления между двумя вершинами.одна сторона. код показывает, как показано ниже:

public class Graph {

    // 顶点个数（顶点编号从0开始，在本文例子中，编号为0的顶点不存在）
    private int v;

    // 记录每个顶点的边
    private LinkedList<Edge>[] adj;

    public Graph(int v) {
        this.v = v;
        // 初始化
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();
        }
    }

    // 添加一条边，从s到达t
    public void addEdge(int s, int t, int weight) {
        Edge edge = new Edge(s, t, weight);
        adj[s].add(edge);
    }
}

После определения информации описания графа следующим шагом является реализация алгоритма Дейкстры с помощью кода.Код и комментарии следующие.

Есть две логики, чтобы объяснить немного. Первое место: массив флагов записывает пройденные вершины, чтобы предотвратить бесконечные циклы, например, если вершина 1 может достичь 2, мы тогда определим, до каких точек может добраться 2, вершина 1 может достичь 5, а 5 также может достичь 2. , если нет массива флагов для записи вершины 2, которую мы прошли, то мы продолжим обход 2, что вызовет бесконечный цикл. Второе место: массив предшественников записывает информацию о пути, индекс массива представляет собой номер вершины, а значение элемента представляет, какая вершина достигает текущей вершины, например: предшественница[3]=1 означает, что она достигнута через вершину 1 Вершина 3.

// 采用迪杰斯特拉算法找出从s到t的最短路径
public void dijkstra(int s, int t) {
    int[] dist = new int[v];    // 记录s到每个顶点的最小距离，数组下标表示顶点编号，值表示最小距离
    boolean[] flag = new boolean[v];    // 记录遍历过的顶点，数组下标表示顶点编号，值表示是否遍历过该顶点
    for (int i = 0; i < v; i++) {
        dist[i] = Integer.MAX_VALUE;    // 初始状态下，将顶点s到其他顶点的距离都设置为无穷大
    }
    int[] predecessor = new int[v];     // 记录路径，索引表示顶点编号，值表示到达当前顶点的顶点是哪一个
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    dist[s] = 0;    // s->s的路径为0
    while (!queue.isEmpty()) {
        Integer vertex = queue.poll();
        if (flag[vertex]) continue; // 已经遍历过该顶点，就不再遍历
        flag[vertex] = true;
        for (int i = 0; i < adj[vertex].size(); i++) {
            Edge edge = adj[vertex].get(i);
            if (dist[vertex] < (dist[edge.t] - edge.weight)) {  // 如果出现了比当前路径小的方式，就更新为更小路径
                dist[edge.t] = dist[vertex] + edge.weight;
                predecessor[edge.t] = vertex;
            }
            queue.add(edge.t);
        }
    }
    // 打印路径
    System.out.println("最短距离：" + dist[t]);
    System.out.print(s);
    print(s, t, predecessor);
}

Функция функции печати состоит в том, чтобы напечатать, какие точки должны пройти через кратчайший путь от вершины s до вершины t. Конкретный код выглядит следующим образом, это рекурсивный вызов, который относительно прост:

// 打印路径
private void print(int s, int t, int[] predecessor) {
    if (t == s) {
        return;
    }
    print(s, predecessor[t], predecessor);
    System.out.print(" -> " + t);
}

контрольная работа

По примеру в тексте построим график и протестируем результат, код такой:

public static void main(String[] args) {
    // 构建图
    Graph graph = new Graph(7);
    graph.addEdge(1, 2, 60);
    graph.addEdge(1, 3, 10);
    graph.addEdge(1, 5, 50);
    graph.addEdge(2, 4, 35);
    graph.addEdge(3, 4, 30);
    graph.addEdge(3, 5, 25);
    graph.addEdge(4, 6, 15);
    graph.addEdge(5, 2, 30);
    graph.addEdge(5, 6, 105);
    // 计算最短距离
    graph.dijkstra(1, 6);
}

Результаты теста:

Суммировать

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