Newsgroup: it.scienza.informatica
Titolo: algoritmo contrario a dijkstra : dati i percorsi minimi calcolare i pesi.

Salve,
Ho un problema che mi piacerebbe risolvere un po' insolito:
Dato un grafo ovvero dei nodi e degli archi con peso (da assegnare)
e non orientati;
Definiti i cammini minimi fra varie coppie (non necessariamente tutte)
di nodi di questo grafo.
Si vuole assegnare il peso ad ogni arco affinche le coppie di cammini
minimi prima citati siano veramente tali.
Cosa mi consigliate?
Io avrei pensato di procedere in questo modo:
Per ogni cammino es: a-b-c-d
calcolo tutti i percorsi che vanno da 'a' a 'b' e per ognuno di questi
percorsi p impongo che:
costo di p>costo di a-b
faccio la stessa cosa per a-c
e impongo per tutti i percorsi p che vanno da a a c:
costo di p>costo di a-b-c
faccio la stessa cosa per a-d
costo di p>costo di a-b-c-d
E questo per ogni percorso che definisco minimo.
In questo modo ho un sistema di disequazioni in cui aggiungendo
una funzione obiettivo (es. minimizzare il costo dei pesi)
potrei risolvere il problema con il metodo del simplesso.
Ma il sistema che ne viene fuori e' troppo grande!
(i nodi sono circa 20 e gli archi circa 100 i percorsi sono circa 50)
e poi dove trovo tool per risolvere il problema del simplesso?
C'e' un altro algoritmo?
Cosa mi consigliate?
Come potri risolvere il problema?
Grazie in anticipo per il tempo che mi dedicherete,
Mario.

 Cosa mi consigliate?
Ciao,
intanto mi viene in mente una situazione per cui un grafo con cammini
minimi
"assegnati" non possa essere reso tale:
siano W,X ed Y nodi, c, c' e c'' percorsi. se consideriamo il grafo:
     c''        c'
W ------ X ------- Y
            |______|
                c
allora se volessimo che da X ad Y il percorso + breve č c e da W a Y
č (c'' , c') saremmo fregati. Infatti:
peso(c) < peso(c')
peso(c'')+peso(c') < peso(c'') + peso(c)
E questo porta all'irrisolvibilitŕ del problema. Non considerando
questi tipi di istanze,
penso che si potrebbe procedere nel seguente modo:
basta assegnare ad ogni arco appartenente ad uno dei cammini minimi un
peso costante (indichiamolo con a e poniamo la condizione che a sia
diverso da 0).
Se c* č il cammino minimo + lungo,
allora sia w = |c*| * a + 1. Poni w come peso di ogni altro arco del
grafo (cioč, w č il peso di ogni arco del grafo che non appartiene ad
un cammino minimo).
E' corretto questo algoritmo? Ovvero:ogni cammino minimo assegnato
rimane minimo
dopo la sua esecuzione?
Proviamo a capirlo. Siano A e B due nodi e c il cammino minimo
assegnato. Sia c'
un cammino di peso ancora piů piccolo (dopo l'esecuzione
dell'algoritmo): peso(c') <= peso(c). Nota che tutti gli archi di c
hanno peso pari a: a.
Se č cosě, qualche arco di c' avra un valore diverso da a (e pari a
w). Se cosě nn fosse, allora ci troveremmo in una situazione simile a
quella del grafo precedentemente descritto, ma che abbiamo deciso di
escludere a priori. Perciň, il peso di c' nn puň essere minore del
peso di c per la presenza di uno o piů archi con peso w.
La completezza sarebbe importante da stabilire. Cioč: dato un grafo
con cammini
minimi assegnati e per cui si sappia che sia possibile effettuare un
assegnamento di
pesi, questo algoritmo restituisce un risultato corretto? Se l'analisi
dei casi che impediscono l'assegnamento dei pesi effettuata
precedentemente fosse corretta e completa, allora penso che questo
algoritmo possa funzionare.
Prendi con le pinze quello che ho scritto. Potrebbero esserci errori
che rendono
tale algoritmo non funzionante, o magari mi sfugge qualcosa a me,  ma
potrebbe essere comunque un punto di partenza. ;)
Mi riservo di pensarci ancora un pň su e di apportare eventuali
correzioni. 
Ciao

 un cammino minimo).
Questo algoritmo funziona per i casi piu' semplici, dove i cammini sono
separati e non si intersecano.
Es.
nel caso:
A---x---B----y----C---z--F---w------D--p--G
        |                           |
        |                           |
        j                           |
        |                           |
        |                           |
        E----------k-----------------
dove ABCDEFG sono i nodi e xywjkzp i pesi
se definissi i cammini minimi ABCFDG
e ABED il tuo algoritmo non funzionerebbe poiche' j+k<y+z+w
e quindi il cammino A->D diventerebbe minimo per ABED
Grazie per avermi risposto.
Mario.

minimi prima citati siano veramente tali.<snip>
Mettendo peso 0 a tutti gli archi, tutti i cammini sono minimi,
compresi quelli definiti.
A meno che te non voglia che i cammini da te definiti siano anche gli
unici possibili, o che il peso deve essere >0, ma questo non e' stato
specificato.