Newsgroup: it.comp.programmare
Titolo: grafi e cammini minimi

Vorrei trovare il numero di cammini minimi tra 2 vertici utilizzando
algoritmo di Dijkstra
Ovviamente sto parlando di grafi orientati e pesati e senza archi negativi.
Qualcuno ha qualche idea anche vaga?


Che intendi ?
Qualche idea su come realizzare Dijkstra in qualche linguaggio di
programmazione ? Oppure qualche idea su come funziona l'algoritmo ?
Ciao
    Riccardo


Qualche idea pertrovare il numero di cammini minimi tra 2 nodi di un
grafo....pensavo di farlo modificando l'algoritmo di Dijkstra che già
conosco.

 conosco
Se vuoi ti posso descrivere un algoritmo di Dijkstra per trovare i cammini
minimi su un grafo orientato con archi con pesi non negativi...
r è il nodo di partenza
d è un vettore che contiene i cammini minimi da r ad ogni altro nodo
pred è il vettore che contiene il cammino fatto. Ad esempio pred[i] contiene
il nodo che precede i nel cammino
c è la matrice dei pesi
1) S = vuoto, V = tutti i nodi, , d[i] = +infinito (o la somma di tutti i
pesi degli archi + 1) per ogni nodo, d[r] = 0, pred[r] = 0
2) Finchè in S non ci sono tutti i nodi
        i è l'indice del vettore d tale che d[i] è il minimo elemento del
vettore d per i nodi contenuti in V
        togli i da V
        aggiungi i a S
        per ogni arco (i,j) appertenente alla Forward Star di i (cioè per
ogni arco uscente da i)
                se d[j] > d[i] allora
                    d[j] = d[i] + c[i][j]
                    pred[j] = i
Spero che ti sia stato d'aiuto...forse il corso di Rcerca Oerativa è stato
utile...
Ciao
        Riccardo

Mi sa che ho fatto casino...
c è la matrice dei costi...
per pesati intendevi dire che ogni nodo ha un peso ?
Allora ad esempio potresti utilizzare un simplesso per flussi...
Ciao

 ha scritto nel messaggio
news:k0l37.62867$cd.4...@news1.tin.it...

si pesi degli archi....penso che c[i][j] possa essere sostituito da w[i][j]
la matrice dei pesi...comunque Dijkstra lo conosco abbastanza bene.
Volevo solo trovare il numero di cammini minimi tra il vertice sorgente e
un'altro vertice v scelto passato come parametro alla funzione.

 un'altro vertice v scelto passato come parametro alla funzione.
Ah...ok...quindi tu per pesi intendevi i costi (i pesi sono sui nodi e i
costi sono sugli archi)...
Trovare il numero di cammini minimi è molto diverso dal trovare un solo
cammino minimo...
Per trovare tutti i cammini minimi credo che tu possa fare una cosa del
genere...
C'e' un cammino alternativo se ci sono più indici per cui si ottiene il
minimo di d per i nodi in V...mettiamo che questi indici siano 2 : x e y...
Esegui la risoluzione due volte...nel primo caso imponi i = x e nel secondo
caso imponi i = y...per ogni cammino ci possono essere altre
diramazioni...anche molte...
Non è così semplice...forse sarebbe più semplice organizzare Dijkstra in
modo ricorsivo...
Potresti fare una cosa del genere...te los crivo in uno pseudo linguaggio...
int dijkstra(int *S, int *V, int *d, int *pred, int numNodi )
{
  se in S ci sono tutti i nodi allora
        return 1;
  S1 = S;
  V1 =V;
  pred1 = pred;
  d1 = d;
  int totaleCammini = 0;
  per ogni indice i tale che d[i] = min d per gli indici in V
  {
        S1 = S + {i};
        V1 = V - {i};
        aggiorni d1 e pred1 secondo l'algoritmo (sempre riferendoti ai
valori iniziali d e pred)
        totaleCammini += dijkstra(S1, V1, d1, pred1, numNodi);
  }
}
in questo modo lanciando questa funzione dovresti esplorare tutti i
cammini...ed ottenere come valore di ritorno il numero di cammini...
Non so se volevi questa roba in C...se non ci capisci dimmelo...
Ciao
        Riccardo

 }
Manca un return totaleCammini in fondo...
Ciao

nel cercare informazioni, visto che sto cercando di sviluppare un'applet
Java su Dijkstra mi sono imbattuto nella vostra discussione.
E mi chiedevo non sarà che per caso conoscete o mi potete passare
una qualche applet giusto per farmi un idea, come esempio insomma,
grazie in anticipo.
Ciao a presto!

 ha scritto nel messaggio
news:9jja3g$8fe$1...@nreadB.inwind.it...

Sorry...non ho applet di esempio...
Prova a seguire passo passo l'algoritmo...e a scrivere il codice relativo ad
ogni passo...dovrebbe essere abbastanza semplice...
Ciao
        Riccardo

grazie molte riccardo, seguirň il tuo consiglio ...

Solamnia wrote:

non ho applet, però qui puoi trovare una esauriente dispensa su Dijkstra:
http://ioi.dsi.unimi.it
Ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it