[C] Grafi - cammini

[andrea0032]

Ciao a tutti, volevo chiedere se esiste, così come esistono algoritmi per il calcolo del cammino minimo di un nodo di un grafo verso gli altri nodi, un algoritmo per il calcolo del cammino massimo, in grafi che possono contenere cicli.

Grazie mille

[71104]

Originariamente inviato da andrea0032

Ciao a tutti, volevo chiedere se esiste, così come esistono algoritmi per il calcolo del cammino minimo di un nodo di un grafo verso gli altri nodi, un algoritmo per il calcolo del cammino massimo, in grafi che possono contenere cicli.

gli archi possono avere pesi negativi?

[andrea0032]

Beh nel mio caso no

[cionci]

Il cammino massimo per grafi che contengono cicli è infinito...altrimenti cosa intendi per cammino massimo ?

[andrea0032]

Si certo, però intendevo cammini semplici ovvero passo su un nodo una e una sola volta.

[cionci]

Originariamente inviato da andrea0032

Si certo, però intendevo cammini semplici ovvero passo su un nodo una e una sola volta.

Se ci sono cicli è impossibile passare una e una sola volta da tutti i nodi, se si vogliono coprire tutti gli archi.

[andrea0032]

Originariamente inviato da cionci

Se ci sono cicli è impossibile passare una e una sola volta da tutti i nodi, se si vogliono coprire tutti gli archi.

Per ogni cammino, passo su un nodo solo una volta. Altrimenti se passo due volte sullo stesso nodo, vuol dire che ho incluso un ciclo nel cammino.

[Unrue]

Originariamente inviato da andrea0032

Per ogni cammino, passo su un nodo solo una volta. Altrimenti se passo due volte sullo stesso nodo, vuol dire che ho incluso un ciclo nel cammino.

Allora il tuo è un problema di copertura del grafo non di "cammino massimo"..

[astorcas]

mmm non ho capito bene se quello che cerchi è il Minimum Spanning Tree o una cosa del tipo arriva dal nodo A a quello B facendo la strada più lunga...