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

C# - Algoritmi sui grafi

C#

L'algoritmo di Floyd-Warshall

Introduzione

  • L'algoritmo di Floyd-Warshall calcola il cammino minimo (o costo minimo) per tutte le coppie di nodi di un grafo pesato e orientato. L’algoritmo funziona anche se ci sono archi con costo negativo; l’importante è che non esistano circuiti con costo totale negativo (perché il problema non sarebbe ben definito).
  • Se il grafo è composto da n nodi, il grafo può essere descritto con una matrice che contiene i costi per tutti i cammini da un nodo ad un altro nodo: è quindi una matrice con n righe e n colonne. Questa è la matrice di input. La diagonale principale della matrice contiene tutti valori nulli: infatti rappresenta il costo da un nodo a sé stesso che è nullo. Due nodi senza collegamento diretto hanno costo infinito.
  • Al termine dell’algoritmo, si ottiene una matrice di output (con la stessa dimensione della matrice di input) che contiene i costi minimi per tutte le coppie di nodi. Nessuna coppia di questa matrice ha costo infinito, in quanto il grafo è connesso.
  • Breve spiegazione dell'algoritmo. Si tratta di un triplo ciclo for: i due cicli più interni individuano la cella di coordinate i, j, mentre il ciclo esterno è il passo dell'algoritmo. Ad ogni passo si verifica se la distanza tra i e j nella matrice dei dati è inferiore alla distanza passando per il nodo k. In caso affermativo di scrive la nuova distanza nella matrice.
  • Una volta ottenuta la matrice di output si hanno le distanze minime tra tutte le coppie di nodi, ma non si sa quali siano i percorsi effettivi minimi. Per questo nell'algoritmo è presente un'altra matrice con i predecessori: nelle coordinate i, j di questa matrice è presente l'indice del nodo precedente. Con questa matrice si possono ricostruire i tutti i percorsi minimi.


Esempio
  • Sia dato il grafo seguente.



  • Si hanno i cinque nodi A, B, C, D ed E. Alcuni di questi nodi sono collegati tra loro; la freccia indica la direzione del collegamento. Il numero vicino alla freccia indica il costo o la lunghezza del collegamento. Alcune coppie di nodi non sono collegati tra loro: per esempio i nodi B e E non hanno un collegamento diretto. Dove non si ha un collegamento diretto si assume un costo del collegamento pari a infinito, che in .NET diventa Int32.MaxValue.
  • Questa è la matrice di input.



  • In questa matrice ci sono i costi di collegamento tra tutte le coppie. Per esempio l’arco che collega il nodo A con il nodo B si trova nella riga A e nella colonna B e vale 8. L’arco opposto che collega il nodo B con il nodo A si trova nella riga B e nella colonna A e vale 7. Il collegamento dei nodi con sé stessi vale 0, mentre i collegamenti che non esistono valgono infinito.
  • Questa è la matrice di output.



  • In questa matrice ci sono i costi minimi di collegamento tra tutte le coppie di nodi dopo aver utilizzato l’algoritmo di Floyd-Warshall. Per esempio la cella di riga A e colonna C è 14; ciò vuol dire che per andare da A a C il costo minimo è 14.
  • La matrice precedente non dà alcuna informazione di quale sia il percorso minimo da un nodo ad un altro nodo, ma dà solo la distanza minima tra i due nodi. L'algoritmo però calcola anche un'ulteriore matrice (detta matrice dei predecessori) che permette di ricostruire i percorsi minimi tra due qualsiasi nodi.

L'algoritmo in C#
  • La funzione che implementa l’algoritmo di Floyd-Warshall è la seguente.

   private static void FloydWarshall(int[,] dati, int[,] pred)
   {
       int dim = dati.GetLength(0);
 
       for (int k = 0; k < dim; k++)
       {
           for (int i = 0; i < dim; i++)
           {
               for (int j = 0; j < dim; j++)
               {
                   if (dati[i, k] != Int32.MaxValue && dati[k, j] != Int32.MaxValue)
                   {
                       if (dati[i, j] > dati[i, k] + dati[k, j])
                       {
                           dati[i, j] = dati[i, k] + dati[k, j];
                           pred[i, j] = pred[k, j];
                       }
                   }
               }
           }
       }
   }

  • Essa ha come parametri di input due array a due dimensioni. Il primo è la matrice di input, essa viene modificata dalla funzione stessa e diventa quindi anche la matrice di output. Il secondo parametro è la matrice dei predecessori, anche questa viene modificata dalla funzione stessa.
  • Ecco come utilizzare questa funzione con l’esempio del grafo precedente.

   // Matrice delle distanze
   int[,] dist = new int[5, 5];

   // Matrice dei predecessori
   int[,] pred = new int[5, 5];
 
   // Inizializza la matrice delle distanze
   dist[0, 0] = 0; dist[0, 1] = 8; dist[0, 2] = Int32.MaxValue;
   dist[0, 3] = Int32.MaxValue; dist[0, 4] = 9;
   dist[1, 0] = 7; dist[1, 1] = 0; dist[1, 2] = Int32.MaxValue;
   dist[1, 3] = 5; dist[1, 4] = Int32.MaxValue;
   dist[2, 0] = 6; dist[2, 1] = Int32.MaxValue; dist[2, 2] = 0;
   dist[2, 3] = Int32.MaxValue; dist[2, 4] = Int32.MaxValue;
   dist[3, 0] = Int32.MaxValue; dist[3, 1] = Int32.MaxValue; dist[3, 2] = 4;
   dist[3, 3] = 0; dist[3, 4] = 3;
   dist[4, 0] = Int32.MaxValue; dist[4, 1] = Int32.MaxValue; dist[4, 2] = 5;
   dist[4, 3] = Int32.MaxValue; dist[4, 4] = 0;
 
   // Inizializza la matrice dei predecessori
   for (int i = 0; i < 5; i++)
   {
       for (int j = 0; j < 5; j++)
       {
           pred[i, j] = i;
       }
   }

   // Esegue l'algoritmo
   FloydWarshall(dist, pred);

   // Mostra la matrice delle distanze
   Console.WriteLine("Matrice distanze:");
   for (int i = 0; i < 5; i++)
   {
       for (int j = 0; j < 5; j++)
       {
           Console.Write(dist[i, j] + "\t");
       }
       Console.WriteLine();
   }
 
   // Mostra la matrice dei predecessori
   Console.WriteLine("Matrice predecessori:");
   for (int i = 0; i < 5; i++)
   {
       for (int j = 0; j < 5; j++)
       {
           Console.Write(pred[i, j] + "\t");
       }
       Console.WriteLine();
   }
 
   // Esempio di ricostruzione di un percorso
   // Da E (indice 4) a B (indice 1)
   List<string> nodi = new List<string>() { "A", "B", "C", "D", "E" };
   int ii = 4;
   int jj = 1;
   Console.WriteLine("Percorso inverso da {0} a {1}:", nodi[ii], nodi[jj]);
   Console.Write(nodi[jj] + "\t");   // Ultimo
   while (pred[ii, jj] != ii)
   {
       Console.Write(nodi[pred[ii, jj]] + "\t");
       jj = pred[ii, jj];
   }
   Console.Write(nodi[ii] + "\t");   // Primo
 
  • L’output in Console è la matrice di output:

Matrice distanze:
0 8 14 13 9
7 0 9 5 8
6 14 0 19 15
10 18 4 0 3
11 19 5 24 0
Matrice predecessori:
0 0 4 1 0
1 1 3 1 3
2 0 2 1 0
2 0 3 3 3
2 0 4 1 4
Percorso inverso da E a B:
B A C E

L'algoritmo di Kruskal
Introduzione
  • L'algoritmo di Kruskal permette di determinare l’albero di copertura minimo (minimum spanning tree, MST) in un grafo non orientato con archi pesati non negativi.
  • La soluzione dell’algoritmo è ottima (e possono esserci più soluzioni ottime).
  • L’idea dell’algoritmo è di costruire un sottoinsieme degli archi di collegamento aggiungendo un arco per volta. Si considerano gli archi ordinandoli in base alla loro lunghezza (cioè al loro peso o costo) in modo crescente. Si aggiunge l’arco in esame al sottoinsieme solo se non crea circuiti chiusi. Si dimostra che questo algoritmo dà la soluzione ottima.

Esempio
  • Si voglia trovare l’albero di copertura minimo per il grafo seguente.


 
 
  • Il grafo è descritto completamente dai nodi e dagli archi, perciò la funzione che implementa l’algoritmo necessita di queste informazioni che si decide di modellizzare con una semplice classe di oggetti chiamati ‘KruskalEdge’ (ogni oggetto rappresenta un arco che collega due nodi).
  • Ogni oggetto ha le seguenti proprietà: gli indici dei nodi collegati dall’arco (due numeri interi compresi tra 0 e il numero dei nodi - 1), la lunghezza dell’arco (un valore intero) e un boolean che indica se l’arco fa parte dell’albero minimo oppure no (inizializzato a false). Si chiamano queste proprietà rispettivamente: ‘Node1’, ‘Node2’, ‘Value’ e ‘Selected’.
  • La classe che genera questi oggetti è la seguente:

   class KruskalEdge
   {
       public int Node1 { get; set; }
       public int Node2 { get; set; }
       public int Value { get; set; }
       public bool Selected { get; set; }
   }

  • Per esempio l’arco di collegamento tra A e C di lunghezza 9 è descritto dall’oggetto seguente (il nodo A ha indice 0, il nodo C ha indice 2):

   new KruskalEdge() { Node1 = 0, Node2 = 2, Value = 9, Selected = false }

  • La funzione 'Kruskal' che implementa l’algoritmo, ha come unico parametro una lista di oggetti di tipo ‘KruskalEdge’; la funzione ne modifica la sola proprietà ‘Selected’ degli oggetti.
  • Questa funzione innanzi tutto ordina la lista di oggetti in base alla lunghezza degli archi (proprietà ‘Value’). Poi cicla tutti gli archi e imposta la proprietà ‘Selected’ a true solo se l’arco non crea un circuito chiuso. È necessario gestire il sottoinsieme dei nodi che vengono compresi nell’albero minimo; man mano che l’algoritmo procede, possono esserci più sottoinsiemi non connessi che vengono poi uniti. La struttura dati scelta per questa gestione è una lista (1) di liste (2) di numeri interi. Ogni elemento della lista (1) è un insieme di nodi connessi tra loro (senza anelli), mentre ogni lista (2) è l’elenco dei nodi. Ogni volta che si esamina un arco, occorre capire se i nodi dell’arco sono presenti in qualche lista. Ci sono 5 casi:
    • a) Nodi non compresi in nessuna lista: si aggiunge alla lista (1) una nuova lista con i due soli nodi.
    • b) Il primo nodo è presente in una lista, il secondo no: si aggiunge il secondo nodo alla lista.
    • c) Il secondo nodo è presente in una lista, il primo no: si aggiunge il primo nodo alla lista.
    • d) I nodi sono presenti nella stessa lista: non si fa niente perché l’arco che collega i nodi creerebbe un circuito chiuso. Si lascia la proprietà ‘Selected’ dell’arco a false.
    • e) I nodi sono presenti in liste diverse: si fondono le due liste.
  • Ecco la funzione che implementa l’algoritmo di Kruskal.

   private void Kruskal(List<KruskalEdge> list)
   {
       // Ordinamento della lista degli archi
       list = list.OrderBy(p => p.Value).ToList();
 
       // Definizione dove tenere i percorsi connessi
       List<List<int>> nodi = new List<List<int>>();
 
       // Qua inizia l'algoritmo, si analizza un arco per volta
       for (int i = 0; i < list.Count; i++)
       {
           int nodo1 = list[i].Node1;
           int nodo2 = list[i].Node2;

           // Se cerca se il nodo1 è in una delle liste dei nodi (altrimenti -1)
           int indexNodo1 = -1;
           for (int j = 0; j < nodi.Count; j++)
           {
               if (nodi[j].Contains(nodo1))
               {
                   indexNodo1 = j;
                   break;
               }
           }
 
           // Se cerca se il nodo2 è in una delle liste dei nodi (altrimenti -1)
           int indexNodo2 = -1;
           for (int j = 0; j < nodi.Count; j++)
           {
               if (nodi[j].Contains(nodo2))
               {
                   indexNodo2 = j;
                   break;
               }
           }
 
           if (indexNodo1 == -1 && indexNodo2 == -1)
           {
               // È un nuovo segmento da aggiungere
               nodi.Add(new List<int> { nodo1, nodo2 });
               list[i].Selected = true;
           }
           else if (indexNodo1 != -1 && indexNodo2 == -1)
           {
               // Nodo1 è presente, Nodo2 non è presente: si aggiunge Nodo2
               nodi[indexNodo1].Add(nodo2);
               list[i].Selected = true;
           }
           else if (indexNodo1 == -1 && indexNodo2 != -1)
           {
               // Nodo2 è presente, Nodo1 non è presente: si aggiunge Nodo1
               nodi[indexNodo2].Add(nodo1);
               list[i].Selected = true;
           }
           else if (indexNodo1 == indexNodo2)
           {
               // Nodo1 e Nodo2 sono presenti nella stessa lista: si formerebbe un circuito chiuso, non si aggiunge
           }
           else
           {
               // Nodo1 e Nodo2 sono presenti in liste diverse: si uniscono le due liste
               while (nodi[indexNodo2].Count > 0)
               {
                   nodi[indexNodo1].Add(nodi[indexNodo2][0]);
                   nodi[indexNodo2].RemoveAt(0);
               }
               nodi.RemoveAt(indexNodo2);
               list[i].Selected = true;
           }
       }
   }

  • Utilizzo della funzione.

   // Preparazione lista degli archi
   List<KruskalEdge> list = new List<KruskalEdge>();
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 2, Value = 9, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 3, Value = 9, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 4, Value = 11, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 5, Value = 11, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 6, Value = 10, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 7, Value = 9, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 0, Node2 = 8, Value = 10, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 1, Node2 = 2, Value = 8, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 1, Node2 = 8, Value = 7, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 2, Node2 = 8, Value = 6, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 3, Node2 = 4, Value = 8, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 4, Node2 = 6, Value = 12, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 5, Node2 = 6, Value = 12, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 6, Node2 = 7, Value = 13, Selected = false });
   list.Add(new KruskalEdge() { Node1 = 7, Node2 = 8, Value = 8, Selected = false });
 
   // Esegue l'algoritmo
   Kruskal(list);
 
   // In Console, l'elenco degli archi dell'albero minimo
   for (int i = 0; i < list.Count; i++)
   {
       if (list[i].Selected)
       {
           Console.WriteLine("Arco da nodo {0} a nodo {1}, valore {2}.", list[i].Node1, list[i].Node2, list[i].Value);
       }
   }

  • Output.

   Arco da nodo 0 a nodo 2, valore 9.
   Arco da nodo 0 a nodo 3, valore 9.
   Arco da nodo 0 a nodo 5, valore 11.
   Arco da nodo 0 a nodo 6, valore 10.
   Arco da nodo 1 a nodo 8, valore 7.
   Arco da nodo 2 a nodo 8, valore 6.
   Arco da nodo 3 a nodo 4, valore 8.
   Arco da nodo 7 a nodo 8, valore 8.

  • Nella figura seguente ci sono gli archi dell’albero minimo evidenziati in verde.


© 2020 Carlo Vecchio
Torna ai contenuti