[C] Visita di uno o più grafi per ritrovamento del percorso più conveniente

[be_ar]

Salve a tutti
Vi pongo il mio problema: sto scrivendo un programma per un progetto universitario, che verte sull'implementazione del gioco del Risiko.
Ora, io ho 6 grafi, rappresentati con liste di adiacenza, e ognuno dei quali rappresenta un continente.
La struttura è questa:

typedef struct Tnation
{
     int ID;
     struct Tnation *next;
}Tnation;

typedef Tnation* Pnation;

typedef struct Tcontinent
{
     int n_nations;
     Tnation **nations;
}Tcontinent;

typedef Tcontinent* Pcontinent;

Ogni nazione è collegato con un arco con i suoi confinanti, ed ovviamente, sono presenti anche collegamenti intercontinentali tra nazione e nazione, proprio come sul tabellone del Risiko.

Ho già implementato tutto, ma ora mi manca l'ultima funzione, che sarebbe quella che, date due nazioni (la nazione da dove si vuol far partire l'attacco [di proprietà del giocatore di turno] e la nazione da conquistare), dice all'utente qual è il percorso da seguire più conveniente, in base alle truppe presenti nelle nazioni nemiche che si incontrano per la strada e che si frappongono, appunto, tra la nazione di partenza e quella di arrivo. Tale informazione, è presente in un array di struct che ha questa struttura:

typedef struct Tnations_detail
{
     char name[30]; //Nome della nazione
     int continent;//Appartenenza di una data nazione ad un continente
     int membership; //Appartenenza ad un determinato giocatore
     int N_army; //Numero di armate presenti nella nazione
     int index; //Indice in cui si trova la nazione all'interno dell'array di liste del grafo
}Tnations_detail;

(L'ID della nazione, che è presente anche nei grafi, non è altro che l'indice dell'array+1: l'Alaska, ha ID 1 ed è presente in NATIONS[0]).

In pratica: l'utente X dice di voler attaccare l'Argentina, partendo dalla Cina (trovate un tabellone abbastanza definito qui http://goo.gl/sxCGs). Ora, io dovrei dire all'utente X, che non gli conviene fare un tragitto del tipo Medio Oriente->Egitto->Africa del Nord->Brasile->Argentina (sempre se non ci siano propri possedimenti durante questo percorso, altrimenti, converrebbe attaccare dalla nazione più vicina possibile alla nazione che si vuol conquistare, ma questo è un punto che potrei pure trascurare, in realtà), ma gli conviene fare Mongolia->Kamchatka->[tutta l'America del Nord]->[tutta l'America del Sud]-> Argentina, che, anche se più lungo, contiene un numero di armate totali da affrontare minore che nel primo tragitto, visto che nel primo percorso si dovrebbero affrontare, per dire, 50 armate per raggiungere l'obiettivo, mentre nel secondo ce ne sarebbero 30.

Ho letto dell'algoritmo di Dijkstra, e per quel poco (pochissimo) che c'ho capito, non credo si adatti a questo problema, visto che non mi serve il percorso minimo, ma mi serve stabilire qual è il percorso più conveniente a livello di armate incontrate.

Qualcuno saprebbe aiutarmi?

[be_ar]

Nessuno?

[Laikius91]

Non ho ben capito un paio di cose.. i collegamenti tra le varie nazioni (internazionali e non) sono salvati da qualche parte? Inoltre, hai già implementato un algoritmo che data una nazione di partenza e una di arrivo ti ritorni tutti i possibili percorsi?

[be_ar]

Premetto che il progetto l'ho già consegnato, e questa parte qui non l'ho fatta, mi sono limitato a "costringere" l'utente a darmi delle nazioni confinanti per eseguire gli attacchi, altrimenti, nisba.

Comunque, sì, i collegamenti sono memorizzati, sono degli archi, che vanno dalla nazione x alla nazione y.

La funzione che dici te, non l'ho fatta, pure perché non avrei idea di come farla.

[Laikius91]

Si in effetti la faccenda è un po' complicata.. Si potrebbe cercare di scorrere in modo iterativo o ricorsivo tutti gli archi che partono dalla nazione di partenza: ogni arco porta a un'altra nazione, per ciascuna di queste si rifà la stessa visita su ogni arco e poi si continua fino a trovare la nazione di arrivo. Chiaramente per ogni visita bisogna salvarsi il percorso fatto (che ne so, magari in una lista di nazioni) e alla fine andare a confrontare tutti i percorsi ottenuti, contare per ciascuno quante armate si debbano incontrare e ritornare quello con il numero di armate minore...
Bisogna solo stare molto attenti a come viene effettuata la ricerca, magari come condizione di terminazione di un'ipotetica ricorsione (o forse in questo caso iterazione), oltre al ritrovamento della nazione di arrivo, anche il conteggio di quante nazioni si attraversano (nel senso: dopo tot nazioni attraversate il percorso viene ritenuto troppo lungo e quindi si interrompe la ricerca..). C'è da dire che non stiamo parlando nè di miliardi di percorsi, nè di miliardi di nazioni!