Cammino minimo

[eusebi1]

Problema:

Si dia la soluzione tramite pseudocodice ai seguenti problemi:

1. ricerca dei cammini minimi verso un nodo destinazione singolo dato in input a partire da un nodo qualsiasi del grafo.
Si discutano la complessita e la correttezza della soluzione proposta;

2. ricerca dei cammini piu brevi a partire da una sorgente singola per un DAG, Direct Acyclic Graph. Si discutano la
complessita e la correttezza della soluzione proposta.

Per il punto 1 pensavo di fare la trasposta della matrice di adiacenza e di applicare Dijkstra mentre per il 2 di usare
una BFS e sull' albero risultante calcolare i pesi dei vari cammini.

Cosa ne pensate?

[apatriarca]

Nel primo problema non è chiaro se si sta parlando di grafo orientato o no. Se non è orientato allora il problema corrisponde a trovare il cammino minimo tra il nodo e ogni altro nodo. Se è orientato è necessario invertire tutti gli archi per usare la descrizione precedente.

Per il due mi sembra corretto.

[eusebi1]

Scusami molto ma il grafo come sottolinei tu è orientato. grazie

[apatriarca]

Se il grafo è orientato allora, come ho già scritto nel mio scorso post devi considerare il grafo con tutti gli archi invertiti. A questo punto puoi usare Dijkstra. In altra parole, se hai un arco $A \to B$ di un certo peso $k$ devi prendere in considerazione l'arco $B \to A$ dello stesso peso $k$. Se il grafo è memorizzato come matrice di adiacenza, allora devi in effetti trasporre la matrice.

[eusebi1]

grazie molte penso che vada
non ero sicuro ed avevo anche il dubbio che ci fosse qualcosa di meglio
per queso posto i problemi che risolvo di ASD