Algoritmo de Dijkstra para la representación de listas de adyacencia | Codicioso Algo-8 – Part 1

Recomendamos leer las siguientes dos publicaciones como requisito previo para esta publicación.

  1.  Algoritmos codiciosos | Conjunto 7 (algoritmo de ruta más corta de Dijkstra) 
  2. Gráfico y sus representaciones

Hemos discutido el algoritmo de Dijkstra y su implementación para la representación de gráficos de array de adyacencia . La complejidad temporal para la representación matricial es O(V^2). En esta publicación, se analiza el algoritmo O(ELogV) para la representación de listas de adyacencia.
Como se comentó en el post anterior, en el algoritmo de Dijkstra se mantienen dos conjuntos, un conjunto contiene una lista de vértices ya incluidos en SPT (Shortest Path Tree), y otro conjunto contiene vértices aún no incluidos. Con la representación de lista de adyacencia, todos los vértices de un gráfico se pueden recorrer en tiempo O(V+E) usando  BFS . La idea es atravesar todos los vértices del gráfico usando  BFS y use un Min Heap para almacenar los vértices que aún no se incluyen en SPT (o los vértices para los que aún no se finalizó la distancia más corta). Min Heap se usa como una cola de prioridad para obtener el vértice de distancia mínima de un conjunto de vértices aún no incluidos. La complejidad de tiempo de las operaciones como extract-min y lower-key value es O(LogV) para Min Heap.

Los siguientes son los pasos detallados. 

  1. Cree un Min Heap de tamaño V donde V es el número de vértices en el gráfico dado. Cada Node del montón mínimo contiene el número de vértice y el valor de distancia del vértice. 
  2. Inicialice Min Heap con el vértice de origen como raíz (el valor de distancia asignado al vértice de origen es 0). El valor de distancia asignado a todos los demás vértices es INF (infinito). 
  3. Mientras Min Heap no está vacío, haga lo siguiente:
    1. Extraiga el vértice con el Node de valor de distancia mínima de Min Heap. Sea u el vértice extraído. 
    2. Para cada vértice adyacente v de u, verifique si v está en Min Heap. Si v está en Min Heap y el valor de distancia es mayor que el peso de uv más el valor de distancia de u, actualice el valor de distancia de v.

Entendamos con el siguiente ejemplo. Deje que el vértice fuente dado sea 0 
 

Dijkstra’s Algorithm for Adjacency List Representation

Inicialmente, el valor de distancia del vértice de origen es 0 e INF (infinito) para todos los demás vértices. Por lo tanto, el vértice de origen se extrae de Min Heap y se actualizan los valores de distancia de los vértices adyacentes a 0 (1 y 7). Min Heap contiene todos los vértices excepto el vértice 0. 
Los vértices en color verde son los vértices para los que se finalizan las distancias mínimas y no están en Min Heap
 

Dijkstra’s Algorithm for Adjacency List Representation Step 1

Dado que el valor de distancia del vértice 1 es mínimo entre todos los Nodes en Min Heap, se extrae de Min Heap y se actualizan los valores de distancia de los vértices adyacentes a 1 (la distancia se actualiza si el vértice está en Min Heap y la distancia a través de 1 es más corta que la distancia anterior). Min Heap contiene todos los vértices excepto los vértices 0 y 1.
 

Dijkstra’s Algorithm for Adjacency List Representation Step 2

Elija el vértice con un valor de distancia mínimo desde el montón mínimo. Se selecciona el vértice 7. Entonces min-heap ahora contiene todos los vértices excepto 0, 1 y 7. Actualice los valores de distancia de los vértices adyacentes de 7. El valor de distancia de los vértices 6 y 8 se vuelve finito (15 y 9 respectivamente). 
 

Dijkstra’s Algorithm for Adjacency List Representation Step 3

Elija el vértice con una distancia mínima desde el montón mínimo. Se selecciona el vértice 6. Entonces min-heap ahora contiene todos los vértices excepto 0, 1, 7 y 6. Actualice los valores de distancia de los vértices adyacentes de 6. Se actualiza el valor de distancia de los vértices 5 y 8.
 

Dijkstra’s Algorithm for Adjacency List Representation Step 4

Los pasos anteriores se repiten hasta que el montón mínimo no se vacía. Finalmente, obtenemos el siguiente árbol de ruta más corta.
 

Dijkstra’s Algorithm for Adjacency List Representation Step 5

 A continuación se muestra la implementación del enfoque anterior:

C++

// C / C++ program for Dijkstra's
// shortest path algorithm for adjacency
// list representation of graph
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
// A structure to represent a
// node in adjacency list
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};
 
// A structure to represent
// an adjacency list
struct AdjList
{
     
   // Pointer to head node of list
   struct AdjListNode *head;
};
 
// A structure to represent a graph.
// A graph is an array of adjacency lists.
// Size of array will be V (number of
// vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};
 
// A utility function to create
// a new adjacency list node
struct AdjListNode* newAdjListNode(
                   int dest, int weight)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*)
      malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}
 
// A utility function that creates
// a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*)
            malloc(sizeof(struct Graph));
    graph->V = V;
 
    // Create an array of adjacency lists. 
    // Size of array will be V
    graph->array = (struct AdjList*)
       malloc(V * sizeof(struct AdjList));
 
    // Initialize each adjacency list
    // as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
 
    return graph;
}
 
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src,
                   int dest, int weight)
{
    // Add an edge from src to dest. 
    // A new node is added to the adjacency
    // list of src.  The node is
    // added at the beginning
    struct AdjListNode* newNode =
            newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
 
    // Since graph is undirected,
    // add an edge from dest to src also
    newNode = newAdjListNode(src, weight);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}
 
// Structure to represent a min heap node
struct MinHeapNode
{
    int  v;
    int dist;
};
 
// Structure to represent a min heap
struct MinHeap
{
     
    // Number of heap nodes present currently
    int size;    
   
    // Capacity of min heap
    int capacity; 
   
    // This is needed for decreaseKey()
    int *pos;   
    struct MinHeapNode **array;
};
 
// A utility function to create a
// new Min Heap Node
struct MinHeapNode* newMinHeapNode(int v,
                                 int dist)
{
    struct MinHeapNode* minHeapNode =
           (struct MinHeapNode*)
      malloc(sizeof(struct MinHeapNode));
    minHeapNode->v = v;
    minHeapNode->dist = dist;
    return minHeapNode;
}
 
// A utility function to create a Min Heap
struct MinHeap* createMinHeap(int capacity)
{
    struct MinHeap* minHeap =
         (struct MinHeap*)
      malloc(sizeof(struct MinHeap));
    minHeap->pos = (int *)malloc(
            capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array =
         (struct MinHeapNode**)
                 malloc(capacity *
       sizeof(struct MinHeapNode*));
    return minHeap;
}
 
// A utility function to swap two
// nodes of min heap.
// Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a,
                     struct MinHeapNode** b)
{
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}
 
// A standard function to
// heapify at given idx
// This function also updates
// position of nodes when they are swapped.
// Position is needed for decreaseKey()
void minHeapify(struct MinHeap* minHeap,
                                  int idx)
{
    int smallest, left, right;
    smallest = idx;
    left = 2 * idx + 1;
    right = 2 * idx + 2;
 
    if (left < minHeap->size &&
        minHeap->array[left]->dist <
         minHeap->array[smallest]->dist )
      smallest = left;
 
    if (right < minHeap->size &&
        minHeap->array[right]->dist <
         minHeap->array[smallest]->dist )
      smallest = right;
 
    if (smallest != idx)
    {
        // The nodes to be swapped in min heap
        MinHeapNode *smallestNode =
             minHeap->array[smallest];
        MinHeapNode *idxNode =
                 minHeap->array[idx];
 
        // Swap positions
        minHeap->pos[smallestNode->v] = idx;
        minHeap->pos[idxNode->v] = smallest;
 
        // Swap nodes
        swapMinHeapNode(&minHeap->array[smallest],
                         &minHeap->array[idx]);
 
        minHeapify(minHeap, smallest);
    }
}
 
// A utility function to check if
// the given minHeap is ampty or not
int isEmpty(struct MinHeap* minHeap)
{
    return minHeap->size == 0;
}
 
// Standard function to extract
// minimum node from heap
struct MinHeapNode* extractMin(struct MinHeap*
                                   minHeap)
{
    if (isEmpty(minHeap))
        return NULL;
 
    // Store the root node
    struct MinHeapNode* root =
                   minHeap->array[0];
 
    // Replace root node with last node
    struct MinHeapNode* lastNode =
         minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;
 
    // Update position of last node
    minHeap->pos[root->v] = minHeap->size-1;
    minHeap->pos[lastNode->v] = 0;
 
    // Reduce heap size and heapify root
    --minHeap->size;
    minHeapify(minHeap, 0);
 
    return root;
}
 
// Function to decreasy dist value
// of a given vertex v. This function
// uses pos[] of min heap to get the
// current index of node in min heap
void decreaseKey(struct MinHeap* minHeap,
                         int v, int dist)
{
    // Get the index of v in  heap array
    int i = minHeap->pos[v];
 
    // Get the node and update its dist value
    minHeap->array[i]->dist = dist;
 
    // Travel up while the complete
    // tree is not hepified.
    // This is a O(Logn) loop
    while (i && minHeap->array[i]->dist <
           minHeap->array[(i - 1) / 2]->dist)
    {
        // Swap this node with its parent
        minHeap->pos[minHeap->array[i]->v] =
                                      (i-1)/2;
        minHeap->pos[minHeap->array[
                             (i-1)/2]->v] = i;
        swapMinHeapNode(&minHeap->array[i], 
                 &minHeap->array[(i - 1) / 2]);
 
        // move to parent index
        i = (i - 1) / 2;
    }
}
 
// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
   if (minHeap->pos[v] < minHeap->size)
     return true;
   return false;
}
 
// A utility function used to print the solution
void printArr(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}
 
// The main function that calculates
// distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src)
{
     
    // Get the number of vertices in graph
    int V = graph->V;
   
    // dist values used to pick
    // minimum weight edge in cut
    int dist[V];    
 
    // minHeap represents set E
    struct MinHeap* minHeap = createMinHeap(V);
 
    // Initialize min heap with all
    // vertices. dist value of all vertices
    for (int v = 0; v < V; ++v)
    {
        dist[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v,
                                      dist[v]);
        minHeap->pos[v] = v;
    }
 
    // Make dist value of src vertex
    // as 0 so that it is extracted first
    minHeap->array[src] =
          newMinHeapNode(src, dist[src]);
    minHeap->pos[src]   = src;
    dist[src] = 0;
    decreaseKey(minHeap, src, dist[src]);
 
    // Initially size of min heap is equal to V
    minHeap->size = V;
 
    // In the followin loop,
    // min heap contains all nodes
    // whose shortest distance
    // is not yet finalized.
    while (!isEmpty(minHeap))
    {
        // Extract the vertex with
        // minimum distance value
        struct MinHeapNode* minHeapNode =
                     extractMin(minHeap);
       
        // Store the extracted vertex number
        int u = minHeapNode->v;
 
        // Traverse through all adjacent
        // vertices of u (the extracted
        // vertex) and update
        // their distance values
        struct AdjListNode* pCrawl =
                     graph->array[u].head;
        while (pCrawl != NULL)
        {
            int v = pCrawl->dest;
 
            // If shortest distance to v is
            // not finalized yet, and distance to v
            // through u is less than its
            // previously calculated distance
            if (isInMinHeap(minHeap, v) &&
                      dist[u] != INT_MAX &&
              pCrawl->weight + dist[u] < dist[v])
            {
                dist[v] = dist[u] + pCrawl->weight;
 
                // update distance
                // value in min heap also
                decreaseKey(minHeap, v, dist[v]);
            }
            pCrawl = pCrawl->next;
        }
    }
 
    // print the calculated shortest distances
    printArr(dist, V);
}
 
 
// Driver program to test above functions
int main()
{
    // create the graph given in above fugure
    int V = 9;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 7, 8);
    addEdge(graph, 1, 2, 8);
    addEdge(graph, 1, 7, 11);
    addEdge(graph, 2, 3, 7);
    addEdge(graph, 2, 8, 2);
    addEdge(graph, 2, 5, 4);
    addEdge(graph, 3, 4, 9);
    addEdge(graph, 3, 5, 14);
    addEdge(graph, 4, 5, 10);
    addEdge(graph, 5, 6, 2);
    addEdge(graph, 6, 7, 1);
    addEdge(graph, 6, 8, 6);
    addEdge(graph, 7, 8, 7);
 
    dijkstra(graph, 0);
 
    return 0;
}

Java

import java.io.*;
import java.util.*;
 
class GFG {
    static class AdjListNode {
        int vertex, weight;
 
        AdjListNode(int v, int w)
        {
            vertex = v;
            weight = w;
        }
        int getVertex() { return vertex; }
        int getWeight() { return weight; }
    }
 
    // Function to find the shortest distance of all the
    // vertices from the source vertex S.
    public static int[] dijkstra(
        int V, ArrayList<ArrayList<AdjListNode> > graph,
        int src)
    {
        int[] distance = new int[V];
        for (int i = 0; i < V; i++)
            distance[i] = Integer.MAX_VALUE;
        distance[src] = 0;
 
        PriorityQueue<AdjListNode> pq = new PriorityQueue<>(
            (v1, v2) -> v1.getWeight() - v2.getWeight());
        pq.add(new AdjListNode(src, 0));
 
        while (pq.size() > 0) {
            AdjListNode current = pq.poll();
 
            for (AdjListNode n :
                 graph.get(current.getVertex())) {
                if (distance[current.getVertex()]
                        + n.getWeight()
                    < distance[n.getVertex()]) {
                    distance[n.getVertex()]
                        = n.getWeight()
                          + distance[current.getVertex()];
                    pq.add(new AdjListNode(
                        n.getVertex(),
                        distance[n.getVertex()]));
                }
            }
        }
        // If you want to calculate distance from source to
        // a particular target, you can return
        // distance[target]
        return distance;
    }
 
    public static void main(String[] args)
    {
        int V = 9;
        ArrayList<ArrayList<AdjListNode> > graph
            = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }
        int source = 0;
        graph.get(0).add(new AdjListNode(1, 4));
        graph.get(0).add(new AdjListNode(7, 8));
        graph.get(1).add(new AdjListNode(2, 8));
        graph.get(1).add(new AdjListNode(7, 11));
        graph.get(1).add(new AdjListNode(0, 7));
        graph.get(2).add(new AdjListNode(1, 8));
        graph.get(2).add(new AdjListNode(3, 7));
        graph.get(2).add(new AdjListNode(8, 2));
        graph.get(2).add(new AdjListNode(5, 4));
        graph.get(3).add(new AdjListNode(2, 7));
        graph.get(3).add(new AdjListNode(4, 9));
        graph.get(3).add(new AdjListNode(5, 14));
        graph.get(4).add(new AdjListNode(3, 9));
        graph.get(4).add(new AdjListNode(5, 10));
        graph.get(5).add(new AdjListNode(4, 10));
        graph.get(5).add(new AdjListNode(6, 2));
        graph.get(6).add(new AdjListNode(5, 2));
        graph.get(6).add(new AdjListNode(7, 1));
        graph.get(6).add(new AdjListNode(8, 6));
        graph.get(7).add(new AdjListNode(0, 8));
        graph.get(7).add(new AdjListNode(1, 11));
        graph.get(7).add(new AdjListNode(6, 1));
        graph.get(7).add(new AdjListNode(8, 7));
        graph.get(8).add(new AdjListNode(2, 2));
        graph.get(8).add(new AdjListNode(6, 6));
        graph.get(8).add(new AdjListNode(7, 1));
 
        int[] distance = dijkstra(V, graph, source);
        // Printing the Output
        System.out.println("Vertex  "
                           + "  Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "             "
                               + distance[i]);
        }
    }
}

Python3

# A Python program for Dijkstra's shortest
# path algorithm for adjacency
# list representation of graph
 
from collections import defaultdict
import sys
 
 
class Heap():
 
    def __init__(self):
        self.array = []
        self.size = 0
        self.pos = []
 
    def newMinHeapNode(self, v, dist):
        minHeapNode = [v, dist]
        return minHeapNode
 
    # A utility function to swap two nodes
    # of min heap. Needed for min heapify
    def swapMinHeapNode(self, a, b):
        t = self.array[a]
        self.array[a] = self.array[b]
        self.array[b] = t
 
    # A standard function to heapify at given idx
    # This function also updates position of nodes
    # when they are swapped.Position is needed
    # for decreaseKey()
    def minHeapify(self, idx):
        smallest = idx
        left = 2*idx + 1
        right = 2*idx + 2
 
        if (left < self.size and
           self.array[left][1]
            < self.array[smallest][1]):
            smallest = left
 
        if (right < self.size and
           self.array[right][1]
            < self.array[smallest][1]):
            smallest = right
 
        # The nodes to be swapped in min
        # heap if idx is not smallest
        if smallest != idx:
 
            # Swap positions
            self.pos[self.array[smallest][0]] = idx
            self.pos[self.array[idx][0]] = smallest
 
            # Swap nodes
            self.swapMinHeapNode(smallest, idx)
 
            self.minHeapify(smallest)
 
    # Standard function to extract minimum
    # node from heap
    def extractMin(self):
 
        # Return NULL wif heap is empty
        if self.isEmpty() == True:
            return
 
        # Store the root node
        root = self.array[0]
 
        # Replace root node with last node
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
 
        # Update position of last node
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = self.size - 1
 
        # Reduce heap size and heapify root
        self.size -= 1
        self.minHeapify(0)
 
        return root
 
    def isEmpty(self):
        return True if self.size == 0 else False
 
    def decreaseKey(self, v, dist):
 
        # Get the index of v in  heap array
 
        i = self.pos[v]
 
        # Get the node and update its dist value
        self.array[i][1] = dist
 
        # Travel up while the complete tree is
        # not hepified. This is a O(Logn) loop
        while (i > 0 and self.array[i][1] <
                  self.array[(i - 1) // 2][1]):
 
            # Swap this node with its parent
            self.pos[ self.array[i][0] ] = (i-1)//2
            self.pos[ self.array[(i-1)//2][0] ] = i
            self.swapMinHeapNode(i, (i - 1)//2 )
 
            # move to parent index
            i = (i - 1) // 2;
 
    # A utility function to check if a given
    # vertex 'v' is in min heap or not
    def isInMinHeap(self, v):
 
        if self.pos[v] < self.size:
            return True
        return False
 
 
def printArr(dist, n):
    print ("Vertex\tDistance from source")
    for i in range(n):
        print ("%d\t\t%d" % (i,dist[i]))
 
 
class Graph():
 
    def __init__(self, V):
        self.V = V
        self.graph = defaultdict(list)
 
    # Adds an edge to an undirected graph
    def addEdge(self, src, dest, weight):
 
        # Add an edge from src to dest.  A new node
        # is added to the adjacency list of src. The
        # node is added at the beginning. The first
        # element of the node has the destination
        # and the second elements has the weight
        newNode = [dest, weight]
        self.graph[src].insert(0, newNode)
 
        # Since graph is undirected, add an edge
        # from dest to src also
        newNode = [src, weight]
        self.graph[dest].insert(0, newNode)
 
    # The main function that calculates distances
    # of shortest paths from src to all vertices.
    # It is a O(ELogV) function
    def dijkstra(self, src):
 
        V = self.V  # Get the number of vertices in graph
        dist = []   # dist values used to pick minimum
                    # weight edge in cut
 
        # minHeap represents set E
        minHeap = Heap()
 
        #  Initialize min heap with all vertices.
        # dist value of all vertices
        for v in range(V):
            dist.append(1e7)
            minHeap.array.append( minHeap.
                                newMinHeapNode(v, dist[v]))
            minHeap.pos.append(v)
 
        # Make dist value of src vertex as 0 so
        # that it is extracted first
        minHeap.pos[src] = src
        dist[src] = 0
        minHeap.decreaseKey(src, dist[src])
 
        # Initially size of min heap is equal to V
        minHeap.size = V;
 
        # In the following loop,
        # min heap contains all nodes
        # whose shortest distance is not yet finalized.
        while minHeap.isEmpty() == False:
 
            # Extract the vertex
            # with minimum distance value
            newHeapNode = minHeap.extractMin()
            u = newHeapNode[0]
 
            # Traverse through all adjacent vertices of
            # u (the extracted vertex) and update their
            # distance values
            for pCrawl in self.graph[u]:
 
                v = pCrawl[0]
 
                # If shortest distance to v is not finalized
                # yet, and distance to v through u is less
                # than its previously calculated distance
                if (minHeap.isInMinHeap(v) and
                     dist[u] != 1e7 and \
                   pCrawl[1] + dist[u] < dist[v]):
                        dist[v] = pCrawl[1] + dist[u]
 
                        # update distance value
                        # in min heap also
                        minHeap.decreaseKey(v, dist[v])
 
        printArr(dist,V)
 
 
# Driver program to test the above functions
graph = Graph(9)
graph.addEdge(0, 1, 4)
graph.addEdge(0, 7, 8)
graph.addEdge(1, 2, 8)
graph.addEdge(1, 7, 11)
graph.addEdge(2, 3, 7)
graph.addEdge(2, 8, 2)
graph.addEdge(2, 5, 4)
graph.addEdge(3, 4, 9)
graph.addEdge(3, 5, 14)
graph.addEdge(4, 5, 10)
graph.addEdge(5, 6, 2)
graph.addEdge(6, 7, 1)
graph.addEdge(6, 8, 6)
graph.addEdge(7, 8, 7)
graph.dijkstra(0)
 
# This code is contributed by Divyanshu Mehta

C#

// C# program for Dijkstra's
// shortest path algorithm for adjacency
// list representation of graph
using System;
using System.Collections.Generic;
using System.Linq;
 
public class AdjListNode : IComparable<AdjListNode> {
  private int vertex, weight;
  public AdjListNode(int v, int w)
  {
    vertex = v;
    weight = w;
  }
  public int getVertex() { return vertex; }
  public int getWeight() { return weight; }
  public int CompareTo(AdjListNode other)
  {
    return weight - other.weight;
  }
}
 
class GFG {
  // Function to find the shortest distance of all the
  // vertices from the source vertex S.
  public static int[] dijkstra(
    int V, List<List<AdjListNode> > graph, int src)
  {
    int[] distance = new int[V];
    for (int i = 0; i < V; i++)
      distance[i] = Int32.MaxValue;
    distance[src] = 0;
 
    SortedSet<AdjListNode> pq
      = new SortedSet<AdjListNode>();
    pq.Add(new AdjListNode(src, 0));
 
    while (pq.Count > 0) {
      AdjListNode current = pq.First();
      pq.Remove(current);
 
      foreach(
        AdjListNode n in graph[current.getVertex()])
      {
        if (distance[current.getVertex()]
            + n.getWeight()
            < distance[n.getVertex()]) {
          distance[n.getVertex()]
            = n.getWeight()
            + distance[current.getVertex()];
          pq.Add(new AdjListNode(
            n.getVertex(),
            distance[n.getVertex()]));
        }
      }
    }
    // If you want to calculate distance from source to
    // a particular target, you can return
    // distance[target]
    return distance;
  }
 
  static void Main(string[] args)
  {
    int V = 9;
    List<List<AdjListNode> > graph
      = new List<List<AdjListNode> >();
    for (int i = 0; i < V; i++) {
      graph.Add(new List<AdjListNode>());
    }
    int source = 0;
    graph[0].Add(new AdjListNode(1, 4));
    graph[0].Add(new AdjListNode(7, 8));
    graph[1].Add(new AdjListNode(2, 8));
    graph[1].Add(new AdjListNode(7, 11));
    graph[1].Add(new AdjListNode(0, 7));
    graph[2].Add(new AdjListNode(1, 8));
    graph[2].Add(new AdjListNode(3, 7));
    graph[2].Add(new AdjListNode(8, 2));
    graph[2].Add(new AdjListNode(5, 4));
    graph[3].Add(new AdjListNode(2, 7));
    graph[3].Add(new AdjListNode(4, 9));
    graph[3].Add(new AdjListNode(5, 14));
    graph[4].Add(new AdjListNode(3, 9));
    graph[4].Add(new AdjListNode(5, 10));
    graph[5].Add(new AdjListNode(4, 10));
    graph[5].Add(new AdjListNode(6, 2));
    graph[6].Add(new AdjListNode(5, 2));
    graph[6].Add(new AdjListNode(7, 1));
    graph[6].Add(new AdjListNode(8, 6));
    graph[7].Add(new AdjListNode(0, 8));
    graph[7].Add(new AdjListNode(1, 11));
    graph[7].Add(new AdjListNode(6, 1));
    graph[7].Add(new AdjListNode(8, 7));
    graph[8].Add(new AdjListNode(2, 2));
    graph[8].Add(new AdjListNode(6, 6));
    graph[8].Add(new AdjListNode(7, 1));
 
    int[] distance = dijkstra(V, graph, source);
    // Printing the Output
    Console.WriteLine("Vertex "
                      + " Distance from Source");
    for (int i = 0; i < V; i++) {
      Console.WriteLine(
        "{0}             {1}", i,
        distance[i]);
    }
  }
}
 
// This code is contributed by cavi4762.
Producción

Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

Complejidad de tiempo:  La complejidad de tiempo del código/algoritmo anterior parece O(V^2) ya que hay dos bucles while anidados. Si observamos más de cerca, podemos observar que las declaraciones en el bucle interno se ejecutan veces O (V + E) (similar a BFS). El ciclo interno tiene una operación de disminución de clave() que toma el tiempo O (LogV). Por lo tanto, la complejidad temporal general es O(E+V)*O(LogV), que es O((E+V)*LogV) = O(ELogV). 
Tenga en cuenta que el código anterior utiliza Binary Heap para la implementación de Priority Queue. La complejidad del tiempo se puede reducir a O(E + VLogV) usando Fibonacci Heap. El motivo es que Fibonacci Heap tarda un tiempo O(1) para la operación de reducción de teclas, mientras que Binary Heap tarda un tiempo O(Logn).
Notas: 

  1. El código calcula la distancia más corta pero no calcula la información de la ruta. Podemos crear una array principal, actualizar la array principal cuando se actualiza la distancia (como  la implementación de prim ) y usarla para mostrar la ruta más corta desde el origen hasta los diferentes vértices.
  2. El código es para gráficos no dirigidos, la misma función de Dijkstra también se puede usar para gráficos dirigidos.
  3. El código encuentra las distancias más cortas desde la fuente hasta todos los vértices. Si solo estamos interesados ​​en la distancia más corta desde el origen hasta un solo objetivo, podemos romper el bucle for cuando el vértice de distancia mínima seleccionado sea igual al objetivo (Paso 3.a de un algoritmo).
  4. El algoritmo de Dijkstra no funciona para gráficos con bordes de peso negativos. Para gráficos con bordes de peso negativos,   se puede usar el algoritmo Bellman-Ford , pronto lo discutiremos en una publicación separada.
    Impresión de rutas en el algoritmo  
    de ruta más corta de Dijkstra El algoritmo de ruta más corta de Dijkstra usando el conjunto en STL

Referencias:  
Introducción a los algoritmos por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. 
Algorithms por Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *