universityin-classsubject-2101
2023-11-28
Algoritmi
Grafi
Utilizzeremo
Si definisce la funzione peso
Associa a ogni arco un valore.
Si chiama cammino (path) una sequenza di nodi
con
Peso di un cammino:
Un cammino si dice ciclo se
Una componente connessa è un insieme massimale di vertici che sono mutualmente raggiungibili (esiste un cammino che collega ogni nodo agli altri).
Se un cammino presenta due nodi uguali, allora questo presenta un ciclo al suo interno (e spesso si potrebbe saltare, a seconda dell’applicazione).
Se i cammini presentano un ciclo, questi possono essere infiniti.
Un cammino che non contiene cicli (e quindi nodi duplicati) si dice semplice.
non sono sicuro: La BFS per trovare cammini minimi non è adatta con grafi pesati. Ci potrebbero essere cammini meno costosi con un numero superiore di nodi rispetto ad altri.
La funzione
indica il peso del cammino minimo da
Se ci sono cicli con peso negativo, il problema non è risolvibile. Non esiste un cammino minimo (basterebbe aggiungere un’iterazione del ciclo per ottenere un cammino ancora meno costoso).
Problemi sui cammini minimi
Sorgente singola
consiste nel trovare tutti i cammini minimi dal nodo
Destinazione singola
Il problema della destinazione singola non viene studiato in quanto si possono invertire gli archi e sorgente e destinazione per ottenere un problema analogo a quello della sorgente singola.
Coppia di nodi
Tutte le coppie di nodi
Ordinamento Topologico
Ordina sulla base della topologia:
tutti gli archi del grafo dai vertici ordinati devono andare da sinistra verso destra
Possono esistere più ordinamenti topologici validi.
Dato un grafo, qual è la situazione di un grafo in cui è presente il numero massimo di possibili combinazioni di un valido ordinamento topologico?
Il grafo senza archi.
In presenza di cicli, non esiste un’ordinamento topologico.
Label Correcting
Soluzione al problema della sorgente singola
Algoritmo per ottenere il cammino con peso minimo a partire da un nodo
Nota
Non è un’implementazione vera e propria di un algoritmo. È solo un approccio alla risoluzione del problema dei cammini minimi da sorgente singola. Esistono poi diversi algoritmi che implementano la stessa logica (vedi ad esempio l’algoritmo di Bellman Ford)
Inizialmente
L’algoritmo si basa nel richiamare la funzione relax(u, v, w) che rilassa una coppia di nodi.
Per rilassamento si intende l’operazione così definita:
if (d[v] > d[u] + w(u, v))
d[v] = d[u] + w(u, v);SSSP: Single Source Shortest Path
Algoritmo generico non ottimale:
NAIVE_SSSP(V, E, w, s):
FOR v IN V:
d[v] = +INF
PI[v] = NULL
d[s]=0
WHILE ESISTE (u, v): d[u] > d[v] + w(u, v)
GET (u,v) IN E
RELAX(u, v, w)Il while non si ferma mai se esistono cicli con peso negativo.