📚 Algoritmi

Search

SearchSearch

Cammini Minimi

Mar 06, 2024, 5 min read

Cammini Minimi in un Grafo

  • Si tratta di uno dei problemi di ottimizzazione su grafi più importante e più studiato.

Richiami di Definizioni

  • insieme finito di nodi;
  • tale che per ogni ;
  • La coppia è un grafo orientato:
    • è l’insieme dei nodi di G,
    • è l’insieme degli archi di G.
  • Sia una funzione peso o costo si dice grafo pesato.

Matrice di Adiacenza

  • Dato con la matrice di adiacenza associata a G è la matrice A di dimensioni tale che:

Liste di Adiacenza

  • Dato le liste di adiacenza associate a G sono gli insiemi .

Cammini

  • Sia un grafo con funzione peso
  • Siano . un Cammino da a è una sequenza di nodi contigui di G, cioè tale che:
  • Si usa anche la notazione

Poniamo:

  • Peso del cammimo ;

Poniamo inoltre:

  • PATHS(G) = Insieme di tutti i cammini in G;
  • PATHS(G; u) = insieme di tutti i cammini in G che iniziano da u;
  • PATHS(G; u, v) = insieme di tutti i cammini in G che iniziano da u e terminano in v;

Concatenazione di Cammini

  • Siano e due cammini tali che .
  • Scriviamo per indicare la concatenazione tra i due cammini.
  • Ovviamente il peso del cammino concatenato è la somma dei pesi dei due cammini.

Distanza

  • Poniamo
    • con

Cammini Minimi

  • Un cammino è minimo se

Un Grafo ammette cammini minimi se:

Lemma

Un grafo ammette cammini minimi se e solo se ammette cammini minimi da ciascuno dei suoi nodi

Lemma: Condizione necessaria e sufficiente per cammini minimi

Non vi deve essere alcun ciclo di peso negativo raggiungibile da una sorgente s

Dimostrazione: Necessità

Se da s è possibile raggiungere un ciclo di peso negativo da , allora:

Ma:

Quindi G non ammette cammini minimi da s.

Dimostrazione: Sufficienza

Supponiamo che da s non sia raggiungibile alcun ciclo di peso negativo. 

Per ogni poniamo:

 

è facile verificare che: 

E quindi l’estremo inferiore del peso tra SIMPLE_PATHS e PATHS è uguale. Poiché SIMPLE_PATHS è finito, siamo sicuri che non sarà mai uguale a , da cui:

Data l’arbitrarietà di , concludiamo che G ammette cammini minimi da s.

  • Corollario 1

Condizione necessaria e sufficiente perché un grafo pesato (G,w) ammetta cammini minimi è che non contenga alcun ciclo di peso negativo.

  • Corollario 2

Ogni grafo con funzione peso non negativa ammette sempre cammini minimi.

  • Corollario 3

Ogni grafo aciclico ammette sempre cammini minimi

Sottostruttura Ottima

Sia un cammino minimo in (G,w). 

Allora il sottocammino per ogni è minimo.

Cammini minimi da una singola sorgente

  • Sia (G,w) un grafo pesato, con sorgente assegnata, e supponiamo che (G,w) ammetta cammini minimi da .
  • Vogliamo memorizzare in maniera spazialmente efficiente un cammino minimo da s.
    • La soluzione ingenua consiste nel memorizzare O(n) liste di lunghezza O(n) ciascuna

Grafo dei Cammini Minimi

  • Sia MIN_PATHS(G;s) l’insieme di tutti i cammini minimi da s in G;
  • Sia l’insieme di tutti gli archi contenuti in qualche cammino minimo da s
  • Chiamiamo il grafo grafo dei cammini minimi da s in G

Esempio

Proprietà:

MIN_PATHS(G;s) PATHS() = MIN_PATHS(G;s)

Dimostrazione

wip

Albero di Cammini Minimi

  • Sia (G,w) un grafo pesato, con sorgente assegnata, e supponiamo che (G,w) ammetta cammini minimi da .

Allora esiste un albero , con e radicato in s e contenente esattamente un cammino minimo in G da s per ciascun nodo raggiungibile da s in G.

Dimostrazione

Basta effettura una visita, DFS o BFS, da nel grafo dei cammini minimi .

Complessità Spaziale:

Esempio

Alberi di Cammini Minimi in Grafi non orientati e MST

Dato un grafo non orientato con funzione peso e sorgente , non è necessariamente vero che tra i suoi alberi di cammini minimi da s ci debba essere un MST di (G,w).

(wip)

Further reading

Graph View

Backlinks