Implementación del Algoritmo de Dijkstra

Introducción

En este laboratorio, implementaremos el Algoritmo de Dijkstra en Java. El Algoritmo de Dijkstra es un algoritmo popular utilizado para resolver el problema del camino más corto en un grafo ponderado.

Skills Graph

Crea una clase Graph

En este paso, crearemos una clase llamada Graph que representará nuestro grafo ponderado. Crearemos una matriz de adyacencia bidimensional en esta clase para representar los bordes del grafo.

class Graph
{
    int[][] adjMatrix; // matriz de adyacencia para representar los bordes
    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;
    }
}

Implementa el Algoritmo de Dijkstra

En este paso, implementaremos el algoritmo de Dijkstra en Java. Creemos un método auxiliar llamado getClosestVertex para encontrar el nodo no visitado más cercano. También implementaremos el algoritmo principal en un método dijkstrasShortestPath. Este método tomará un Grafo y un vértice fuente como parámetros y devolverá la matriz de distancias más cortas.

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) {
    // matriz final de distancias más cortas
    int[] distance = new int[g.numOfvertices];
    // matriz para indicar si se ha encontrado la distancia más corta del vértice
    boolean[] visited = new boolean[g.numOfvertices];

    // inicializando las matrices
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // la distancia inicial es infinita
        visited[i] = false; // no se ha encontrado la distancia más corta para ningún nodo todavía
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // obtiene el nodo más cercano
        if(closestVertex == Integer.MAX_VALUE) // si el nodo más cercano está a una distancia infinita, significa que no se puede alcanzar ningún otro nodo. Entonces devuelve
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // la distancia más corta del nodo j no debe haber sido finalizada
            {
                if(g.adjMatrix[closestVertex][j]!= 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // la distancia a través del nodo más cercano es menor que la distancia inicial
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

Prueba nuestra implementación

En este paso, probaremos nuestra implementación creando un método principal que agregará bordes a nuestro grafo y llamará a nuestro método dijkstrasShortestPath para encontrar la distancia más corta desde un vértice fuente hasta todos los demás vértices de un grafo ponderado.

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

    // agrega bordes al grafo
    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);

    // llama al algoritmo de Dijkstra para encontrar la distancia más corta
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

Compila y ejecuta el código anterior para obtener la matriz de distancias más cortas [0, 27, 34, 18, 21, 25].

Resumen

¡Felicidades! Has completado el laboratorio de Implementación del Algoritmo de Dijkstra. Puedes practicar más laboratorios en LabEx para mejorar tus habilidades.