[C++] Cammino minimo in un grafo

[rizz1]

Ciao, volevo chiedere se qualcuno sa un algoritmo per calcolare un cammino minimo tra due nodi del grafo passando per un arco specifico.
In alternativa (essendo il mio grafo orientato) posso sapere un cammino minimo tra due nodi passanti per un nodo specifico.

Un prototipo di funzione potrebbe essere:

cammino(S,D,N);

dove:
S è il nodo sorgente
D è il nodo destinatario
N è il nodo che deve essere visitato nel cammino tra S e D

[Celebron]

così ad occhio io userei uno degli algoritmi classici per stabilire il percorso migliore (dijkstra o bellman-ford) e, a seguire una volta che conosci i pesi effettivi dei vari cammini, controllare con una funzione esaustiva (e ricorsiva) a partire dal miglior cammino disponibile se, in esso, è presente il nodo che ti interessa

ovviamente devi stare attento ai casi particolari. Ad esempio potrebbe essere possibile che il nodo da te richiesto nel cammino in realtà non abbia mai possibilità di esserci. Puoi ottimizzare un po' oppure lasciar fare tutto alla funzione ricorsiva che, da sola, a fine ricorsione esaustiva ti potrà informare sul fatto che tale nodo non è in nessun cammino valido

[rizz1]

Grazie, ora provo a vedere cosa combino prima di porti altri dubbi nel caso ci fossero

[LeleFT]

La letteratura riguardante i grafi e gli algoritmi per i cammini minimi è ampia e su internet si trovano decine di documenti.

Direi che è sufficiente una ricerca con Google, per trovare almeno gli algoritmi (se non proprio i sorgenti).


Devo chiudere.


Ciao.