Implementando o Algoritmo de Dijkstra

Introdução

Neste laboratório, vamos implementar o Algoritmo de Dijkstra em Java. O Algoritmo de Dijkstra é um algoritmo popular usado para resolver o problema do caminho mais curto (shortest-path problem) para um grafo ponderado (weighted graph).

Criar uma Classe Grafo

Nesta etapa, criaremos uma classe chamada Graph que representará nosso grafo ponderado. Criaremos uma matriz de adjacência 2-D nesta classe para representar as arestas (edges) do grafo.

class Graph
{
    int[][] adjMatrix; // matriz de adjacência para representar as arestas
    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;
    }
}

Implementar o Algoritmo de Dijkstra

Nesta etapa, implementaremos o algoritmo de Dijkstra em Java. Vamos criar um método auxiliar chamado getClosestVertex para encontrar o nó não visitado mais próximo. Também implementaremos o algoritmo principal em um método dijkstrasShortestPath. Este método receberá um Graph e um vértice de origem como parâmetros e retornará o array de distâncias mais curtas.

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) {
    // final shortest distance array
    int[] distance = new int[g.numOfvertices];
    // array to tell whether shortest distance of vertex has been found
    boolean[] visited = new boolean[g.numOfvertices];

    // initializing the arrays
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // initial distance is infinite
        visited[i] = false; // shortest distance for any node has not been found yet
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // get the closest node
        if(closestVertex == Integer.MAX_VALUE) // if closest node is infinite distance away, it means that no other node can be reached. So return
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // shortest distance of the node j should not have been finalized
            {
                if(g.adjMatrix[closestVertex][j] != 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // distance via closestVertex is less than the initial distance
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

Testar Nossa Implementação

Nesta etapa, testaremos nossa implementação criando um método main que adicionará arestas (edges) ao nosso grafo e chamará nosso método dijkstrasShortestPath para encontrar a distância mais curta de um vértice de origem para todos os outros vértices de um grafo ponderado.

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

    // add edges to the graph
    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);

    // call Dijkstra's algorithm to find shortest distance
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

Compile e execute o código acima para obter o array de distâncias mais curtas [0, 27, 34, 18, 21, 25].

Resumo

Parabéns! Você concluiu o laboratório de Implementação do Algoritmo de Dijkstra. Você pode praticar mais laboratórios no LabEx para aprimorar suas habilidades.