Pagina personale di:
Carlo Vecchio
appunti di C#, R, SQL Server, ASP.NET, algoritmi, numeri
Vai ai contenuti

C# - Algoritmi sui grafi 2

C#

L'algoritmo di Djkstra

Introduzione

  • L'algoritmo di Dijkstra si applica a un grafo e permette di calcolare il cammino minimo da un nodo a tutti gli altri nodi e ne indica il percorso. I pesi dei nodi sono orientati e non devono essere negativi.
  • Ogni nodo in questo algoritmo ha le seguenti proprietà:
    • Distanza attuale.
    • Flag: Definitivo (true / false se la distanza trovata è quella definitiva).
    • Nodo Predecessore.
  • I passi dell’algoritmo sono i seguenti.
    • Inizializzare il nodo di partenza con Distanza = 0, Definitivo = false, Predecessore = ‘’.
    • Inizializzare tutti gli altri nodi con Distanza = infinita, Definitivo = false, Predecessore = ‘’.
    • Finché ci sono nodi non definitivi:
      • Selezionare il nodo con Distanza minore (quindi si inizia con il nodo di partenza).
      • Impostare per questo nodo il valore Definitivo = true.
      • Aggiornare la Distanza dei nodi collegati a questo nodo selezionato (e che non siano definitivi). Essa va impostata al minimo tra la Distanza attuale del nodo collegato e la Distanza che avrebbe il nodo collegato passando per il nodo selezionato. Se la Distanza viene aggiornata, impostare come Predecessore il nodo selezionato.

Esempio
  • In questo esempio si applica l’algoritmo di Dijkstra per trovare le minime distanze tra il nodo A e gli altri nodi del grafo seguente:


  • Inizializzazione del grafo:



  • Si seleziona il nodo con la distanza minore: A. Si aggiornano (se necessario) i nodi non definitivi ad esso collegati: B e C.



  • Allo stesso modo, si selezionano nell’ordine i nodi: C, B, D, F, E, G e H e si aggiornano (se necessario) i nodi non definitivi ad essi collegati.
  • Nelle immagini seguenti, viene mostrata l'evoluzione dell'algoritmo.















  • L’ultimo grafo è il grafo finale; in ogni nodo è presente la distanza minima dal nodo A e il nodo predecessore.
  • Per esempio, il cammino minimo tra A e H è: A, C, F, G, H.

L'algoritmo in C#
  • Il codice seguente, utilizza le seguenti due classi che definiscono gli oggetti 'Nodo' e 'Collegamento tra due nodi'.

   // Descrive i nodi del grafo: ogni oggetto è un nodo.
   public class DijkstraNode
   {
       public int Node { get; set; }
       public int Distance { get; set; }
       public bool Definitive { get; set; }
       public int Predecessor { get; set; }
   }

   // Descrive i collegamenti tra i nodi del grafo: ogni oggetto è un collegamento tra Node1 e Node2.
   public class DijkstraEdge
   {
       public DijkstraNode Node1 { get; set; }
       public DijkstraNode Node2 { get; set; }
       public int Distance { get; set; }
   }

  • Con il codice seguente, si inizializza una lista con i nodi e una con i collegamenti. Essi sono relativi all'esempio del paragrafo precedente.

   // Preparazione e inizializzazione lista dei nodi.
   List<DijkstraNode> lstNodes = new List<DijkstraNode>();
   for (int i = 0; i <= 7; i++)
   {
       lstNodes.Add(new DijkstraNode() { Node = i, Distance = Int32.MaxValue, Definitive = false, Predecessor = -1 });
   }

   // Preparazione lista degli archi.
   List<DijkstraEdge> lstEdges = new List<DijkstraEdge>();
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[0], Node2 = lstNodes[1], Distance = 8 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[0], Node2 = lstNodes[2], Distance = 6 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[1], Node2 = lstNodes[0], Distance = 5 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[1], Node2 = lstNodes[4], Distance = 7 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[2], Node2 = lstNodes[1], Distance = 4 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[2], Node2 = lstNodes[3], Distance = 4 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[2], Node2 = lstNodes[4], Distance = 6 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[2], Node2 = lstNodes[5], Distance = 5 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[3], Node2 = lstNodes[2], Distance = 4 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[3], Node2 = lstNodes[5], Distance = 3 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[3], Node2 = lstNodes[6], Distance = 6 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[4], Node2 = lstNodes[5], Distance = 2 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[4], Node2 = lstNodes[7], Distance = 5 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[5], Node2 = lstNodes[6], Distance = 2 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[5], Node2 = lstNodes[7], Distance = 5 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[6], Node2 = lstNodes[7], Distance = 2 });
   lstEdges.Add(new DijkstraEdge() { Node1 = lstNodes[7], Node2 = lstNodes[6], Distance = 2 });

   // Esegue l'algoritmo.
   Dijkstra(lstEdges, lstNodes);

   // Stampa il risultato.
   foreach (var node in lstNodes)
   {
       Console.WriteLine(String.Format("Node: {0}   Definitive: {1}   Distance: {2}   Predecessor: {3}", node.Node, node.Definitive, node.Distance, node.Predecessor));
   }

  • Infine, ecco il codice dell'algoritmo vero e proprio.

   private void Dijkstra(List<DijkstraEdge> lstEdges, List<DijkstraNode> lstNodes)
   {
       // Inizializza il nodo di partenza: il primo della lista.
       lstNodes[0].Distance = 0;
 
       // Finché ci sono nodi non definitivi...
       while (lstNodes.Where(p => !p.Definitive).Count() != 0)
       {
           // Seleziona il nodo con distanza inferiore.
           var node = lstNodes.Where(p => !p.Definitive).OrderBy(p => p.Distance).FirstOrDefault();
           if (node != null)
           {
               // Questo nodo diventa definitivo.
               node.Definitive = true;
               // Ricerca di tutti i nodi collegati al nodo selezionato, non definitivi.
               List<DijkstraNode> linkedNodes = lstEdges.Where(p => p.Node1.Node == node.Node).Select(p => p.Node2).Where(p => p.Definitive == false).ToList();
               // Per tutti i nodi collegati:
               foreach (var linkedNode in linkedNodes)
               {
                   // Calcolo della distanza tra il nodo iniziale e 'linkedNode', passando per 'node'.
                   int distanza = node.Distance + lstEdges.Where(p => p.Node1 == node && p.Node2 == linkedNode).First().Distance;
                   // Se la distanza appena calcolata è migliore della distanza attuale:
                   if (distanza < linkedNode.Distance)
                   {
                       // Si aggiorna il 'linkedNode'.
                       linkedNode.Distance = distanza;
                       linkedNode.Predecessor = node.Node;
                   }
               }
           }
           else
           {
               break;
           }
       }
   }


© 2020 Carlo Vecchio
Torna ai contenuti