Pages: [1]   Go Down
Print
Author Topic: Esercizio cammini minimi  (Read 479 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Step91
Matricola
*
Offline Offline

Posts: 14


« on: 06-02-2017, 15:34:11 »

Salve, ho un dubbio riguardante questo esercizio:

Sia G = (V, E) un grafo orientato con una funzione peso a valori reali w : E → R, ma senza cicli di peso negativo.
Siano inoltre a, b, c tre nodi distinti di G.
Si progetti un algoritmo efficiente, valutandone anche la complessit`a computazionale, per determinare (qualora esista) un ciclo di peso minimo (non necessariamente semplice) passante per i tre nodi a, b, c, in un ordine qualsiasi.


L'algoritmo da utilizzare, secondo me, è quello di Bellman-Ford in quanto nel grafo potrei avere archi di peso negativo. Il suddetto algoritmo termina quando trova cicli di peso negativo. Considerando una variante, invertendo i pesi degli archi, esso termina quando trova cicli di peso positivo. Richiamandolo sui tre nodi singoli, A,B,C troviamo i cammini minimi ad essi rispettivi. Ho pensato di inserire un test di ciclicità su questi tre nodi, così da assicurarmi che i tre nodi appartengano al ciclo.

Il mio ragionamento è corretto? O presenta dei punti da correggere?

Spero di non aver fatto figuracce   boh
« Last Edit: 06-02-2017, 23:44:23 by Step91 » Logged
Pages: [1]   Go Up
Print
Jump to: