Реализация алгоритма Дейкстры

Введение

В этом лабе мы собираемся реализовать алгоритм Дейкстры на Java. Алгоритм Дейкстры - это популярный алгоритм, используемый для решения задачи кратчайшего пути в взвешенном графе.

Создайте класс Graph

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

class Graph
{
    int[][] adjMatrix; // матрица смежности для представления ребер
    int numOfvertices;

    Graph(int[][] mat, int v)
    {
        this.adjMatrix = mat;
        this.numOfvertices = v;
    }

    void addEdge(int src, int dest, int edgeWeight)
    {
        adjMatrix[src][dest] = edgeWeight;
        adjMatrix[dest][src] = edgeWeight;
    }
}

Реализуйте алгоритм Дейкстры

В этом шаге мы реализуем алгоритм Дейкстры на Java. Создадим вспомогательный метод под названием getClosestVertex для нахождения ближайшей непосещенной вершины. Также реализуем основной алгоритм в методе dijkstrasShortestPath. Этот метод будет принимать в качестве параметров граф и начальную вершину и возвращать массив с кратчайшими расстояниями.

public static int getClosestVertex(int[] distance, boolean[] visited) {
    int min = Integer.MAX_VALUE;
    int minIdx = -1;
    for(int i=0; i<distance.length; i++) {
        if(distance[i] < min)
            if(visited[i] == false) {
                min = distance[i];
                minIdx = i;
            }
    }
    return minIdx;
}

public static int[] dijkstrasShortestPath(Graph g, int src) {
    // финальный массив с кратчайшими расстояниями
    int[] distance = new int[g.numOfvertices];
    // массив, показывающий, найдено ли кратчайшее расстояние для вершины
    boolean[] visited = new boolean[g.numOfvertices];

    // инициализация массивов
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // начальное расстояние - бесконечность
        visited[i] = false; // кратчайшее расстояние для любой вершины еще не найдено
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // получаем ближайшую вершину
        if(closestVertex == Integer.MAX_VALUE) // если ближайшая вершина находится на бесконечном расстоянии, это означает, что никакая другая вершина не может быть достигнута. Поэтому возвращаем
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // кратчайшее расстояние для вершины j не должно быть окончательно определено
            {
                if(g.adjMatrix[closestVertex][j]!= 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // расстояние через closestVertex меньше начального расстояния
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

Протестируем нашу реализацию

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

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // добавляем ребра в граф
    graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);

    // вызываем алгоритм Дейкстры, чтобы найти кратчайшее расстояние
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

Скомпилируйте и запустите вышеприведенный код, чтобы получить массив кратчайших расстояний [0, 27, 34, 18, 21, 25].

Резюме

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