[Algoritmi] Esercizio relativo agli "shortest path" HELP
Ciao a tutti,
stò impazzendo con questo esercizio di algoritmi. Non chiedo la soluzione (perchè ce l'ho risolto sulle dispense anche se ancora non sono riuscito a capire la soluzione)
Il problema principale è che non riesco proprio a capire come sia fatto questo insieme M a cui ci si riferisce nell'esercizio, allego il testo e sotto di esso posto il mio dubbio...
Esercizio 11 (Shortest-Path set vs. Shortest-Path tree).
M è un insieme di cammini minimi (semplici) del grafo pesato G = (V, E) (privo di cicli di costo negativo) che connettono un nodo s ∈ V con tutti gli altri nodi di V.
Per ogni nodo v in V − s, esiste un cammino in M che raggiunge v inoltre in M non esiste nessun cammino che è sotto-cammino di un altro cammino in M.
Si progetti un algoritmo che, dato M , calcoli un albero dei cammini minimi di G da s.
L’algoritmo deve avere complessità ottima.
Sostanzialmente io ho M che è un INSIEME DI CAMMINI MINIMI CHE PARTONO DA UN NODO SORGENTE s E SONO DIRETTI VERSO TUTTI GLI ALTRI NODI DEL GRAFO G
Da quello che capisco tale insieme M ha la caratteristica di contenere cammini minimi aventi la caratteristica che nessun cammino minimo in M può essere sottocamino minimo di un altro cammino minimo in M
Ma che vuol dire questa cosa? Come deve essere fatto il grafo G?
Faccio un esempio concreto.
Considero il grafo G formato da 4 NODI: V = A, B, C,D
e dai seguenti 3 ARCHI PESATI: E = {(A,B,1); (A,C,2); (B,C,3); (C,D,1)} (il terzo elemento della tripla indica il peso dell'arco in questione).
Facciamo che il mio NODO SORGENTE s sia il nodo A ----> s = A
Ora passiamo a vedere quali sono i CAMMINI MINIMI dal nodo sorgente s verso tutti gli altri nodi e se questi appartengono o no all'insieme M precedentemente descritto:
1) P(A,B): {(A,B,1)} (il cammino minimo da A a B è formato dal solo arco (A,B,1) e pesa appunto 1) ---> P(A,B) APPARTIENE AD M
2) P(A,C): {(A,C,2)} (il cammino minimo da A a C è formato dal solo arco (A,C,12) e pesa appunto 2) ---> P(A,2) APPARTIENE AD M
3) P(A,D): {(A,C,2); (C,D,1)} (il cammino minimo da A a D è formato dall'arco (A,C,2) e dall'arco (C,D,1), quindi ha un peso complessivo pari a 3 ---> P(A,D) NON APPARTIENE AD M perchè l'arco (A,C) facente parte di tale cammino è già presente in M...cioè un sottocammino di P(A,D) è già presente in M
Solo che così mi suona strano...in pratica nell'insieme M avrei tutti cammini aventi lunghezza 1 (tutti cammini composti da solo un arco)
Mi viene in mente che, riferendomi sempre al precedente esempio), in M è presente il cammino P(A,D): {(A,C,2); (C,D,1)} MA NON È PRESENTE IL CAMMINO P(A,C): {(A,C,2)} perchè questo è sottocammino di un altro camino in M
In pratica che se un certo cammino P è più lungo di un altro cammino P' che è suo sottocammino...allora in M c'è P ma non P'
Mi aiutate ad interpretare come è fatto questo insieme M?
Grazie mille
Andrea
stò impazzendo con questo esercizio di algoritmi. Non chiedo la soluzione (perchè ce l'ho risolto sulle dispense anche se ancora non sono riuscito a capire la soluzione)
Il problema principale è che non riesco proprio a capire come sia fatto questo insieme M a cui ci si riferisce nell'esercizio, allego il testo e sotto di esso posto il mio dubbio...
Esercizio 11 (Shortest-Path set vs. Shortest-Path tree).
M è un insieme di cammini minimi (semplici) del grafo pesato G = (V, E) (privo di cicli di costo negativo) che connettono un nodo s ∈ V con tutti gli altri nodi di V.
Per ogni nodo v in V − s, esiste un cammino in M che raggiunge v inoltre in M non esiste nessun cammino che è sotto-cammino di un altro cammino in M.
Si progetti un algoritmo che, dato M , calcoli un albero dei cammini minimi di G da s.
L’algoritmo deve avere complessità ottima.
Sostanzialmente io ho M che è un INSIEME DI CAMMINI MINIMI CHE PARTONO DA UN NODO SORGENTE s E SONO DIRETTI VERSO TUTTI GLI ALTRI NODI DEL GRAFO G
Da quello che capisco tale insieme M ha la caratteristica di contenere cammini minimi aventi la caratteristica che nessun cammino minimo in M può essere sottocamino minimo di un altro cammino minimo in M
Ma che vuol dire questa cosa? Come deve essere fatto il grafo G?
Faccio un esempio concreto.
Considero il grafo G formato da 4 NODI: V = A, B, C,D
e dai seguenti 3 ARCHI PESATI: E = {(A,B,1); (A,C,2); (B,C,3); (C,D,1)} (il terzo elemento della tripla indica il peso dell'arco in questione).
Facciamo che il mio NODO SORGENTE s sia il nodo A ----> s = A
Ora passiamo a vedere quali sono i CAMMINI MINIMI dal nodo sorgente s verso tutti gli altri nodi e se questi appartengono o no all'insieme M precedentemente descritto:
1) P(A,B): {(A,B,1)} (il cammino minimo da A a B è formato dal solo arco (A,B,1) e pesa appunto 1) ---> P(A,B) APPARTIENE AD M
2) P(A,C): {(A,C,2)} (il cammino minimo da A a C è formato dal solo arco (A,C,12) e pesa appunto 2) ---> P(A,2) APPARTIENE AD M
3) P(A,D): {(A,C,2); (C,D,1)} (il cammino minimo da A a D è formato dall'arco (A,C,2) e dall'arco (C,D,1), quindi ha un peso complessivo pari a 3 ---> P(A,D) NON APPARTIENE AD M perchè l'arco (A,C) facente parte di tale cammino è già presente in M...cioè un sottocammino di P(A,D) è già presente in M
Solo che così mi suona strano...in pratica nell'insieme M avrei tutti cammini aventi lunghezza 1 (tutti cammini composti da solo un arco)
Mi viene in mente che, riferendomi sempre al precedente esempio), in M è presente il cammino P(A,D): {(A,C,2); (C,D,1)} MA NON È PRESENTE IL CAMMINO P(A,C): {(A,C,2)} perchè questo è sottocammino di un altro camino in M
In pratica che se un certo cammino P è più lungo di un altro cammino P' che è suo sottocammino...allora in M c'è P ma non P'
Mi aiutate ad interpretare come è fatto questo insieme M?
Grazie mille
Andrea
Risposte
Si ok,
risolto da me...era il secondo dei 2 casi...mi ero confuso...a volte leggere un po' più attentamente serve...
Grazie comunque dell'attenzione
Andrea
risolto da me...era il secondo dei 2 casi...mi ero confuso...a volte leggere un po' più attentamente serve...
Grazie comunque dell'attenzione
Andrea
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo