Minimizzazione del costo massimo

[Itachi-Dev]

Salve, ragazzi ho urgente bisogno di una mano per la soluzione di questo problema:

(Problema risolvibile sia in C++ che in JAVA)

PROBLEMA: MINIMIZZAZIONE DEL COSTO MASSIMO

Sia G = (V,E) un grafo indiretto e connesso dove V è l’insieme dei nodi e E l’insieme degli archi;
Sia L una lista ordinata dei nodi V. Il costo di ogni arco è proporzionale alla distanza nella lista tra
i nodi che lo compongono. In questo modo, in base all’ordinamento
dei nodi nella lista, ogni arco potrà avere un costo differente.
Infine, il costo massimo del grafo cG sarà dato dal costo massimo
presente tra gli archi data una lista L.
Esempio:
La lista dei nodi appartenenti al grafo a destra può essere ordinata
in vari modi:
Per queste liste di esempio abbiamo che nel primo caso i costi dei vari collegamenti sono:
1,3,3,3,5,2,3,2 con il costo massimo (e perciò il costo del grafo) pari a 5, dato dall’arco che collega
il nodo c con il nodo h, e altre due liste dove il costo massimo è di 2 e 6 rispettivamente.
Scrivere un programma che dato un grafo G restituisca una lista L dei nodi V, ordinata in modo tale
che sia minimizzato il costo del grafo cG.

INPUT
L’input consiste in una serie di grafi. Ogni
linea conterrà la rappresentazione di un grafo.
La rappresentazione di un grafo avverrà
elencando tutti gli archi. Ogni arco presente
del grafo sarà separato dal simbolo “;”(punto
e virgola) e l’arco verrà rappresentato dai due
nodi (espressi in ordine alfabetico) divisi dal
simbolo “,”(virgola). Ogni linea terminerà
con il simbolo “.”(punto).
L’ultima riga conterrà la stringa “<END>”.
NOTA: Ogni grafo potrà avere massimo 10
nodi.

OUTPUT
L’output dovrà contenere una linea per ogni
linea di grafo dove viene riportata la lista
ordinata che consente di ottenere il costo
minimo del grafo con il relativo costo. Nota:
se esistono più liste che restituiscono un costo
minimo andrà riportata la prima in ordine
lessicografico.
La lista e il suo relativo costo dovranno essere
rappresentati in output riportando i nodi della
lista divisi dal simbolo “,”(virgola), dopo il
simbolo “=”(uguale) e il costo.

ESEMPIO INPUT
a,b;a,j;b,d;b,g;b,k;c,d;c,f;c,k;c,j;d,f;d,g;e,j;f,g;f,k;f,j;h,k;h,j;k,j.
a,b;a,f;a,h;b,d;b,f;c,e;c,f;c,g;e,f;e,g.
a,b;a,c;a,h;b,c;b,d;c,f;c,g;e,f;e,g;f,h.
a,b;a,d;b,c;b,d;b,e;d,e.
a,b;a,c;b,f;c,d;c,e.
a,b;a,e;a,f;b,d;c,e.
a,b;a,d;a,g;c,e;c,h;e,k;e,j;f,k;g,k.
a,b;a,c;a,d;b,d;d,e.
a,b;a,d;a,f;a,g;b,c;b,f;b,g;b,h;d,e;d,f;d,h;e,f;f,h.
a,b;a,f;a,g;b,c;b,d;b,f;d,e.
a,b;b,c;b,e;d,f;e,f.
<END>

ESEMPIO OUTPUT
b,a,g,d,k,j,f,c,h,e=4
d,h,b,a,f,c,e,g=2
a,b,h,c,d,f,g,e=3
a,d,b,e,c=2
b,a,f,c,d,e=2
b,d,a,e,f,c=2
b,a,d,g,f,k,c,e,h,j=2
b,a,d,c,e=2
c,g,a,b,d,f,h,e=3
c,f,b,a,d,g,e=2
a,b,c,e,d,f=2

Io ho provato a risolverlo ma il mio algoritmo funziona solamente per i grafi che abbiano meno di 7 nodi e non funziona neppure sempre.
Se qualcuno fosse interessato posso spiegare l'algoritmo da me generato e postare il relativo codice.

Grazie in anticipo,
Itachi.