Implementare Algoritmo Di Dijkstra?

[Jim Stacey]

Salve a tutti. Mi trovo molto in difficoltà nell'implementazione (in linguaggio JAVA), del noto algoritmo di Dijkstra, utilizzato per trovare il cammino minimo dal nodo di partenza a quello di arrivo (http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra). Tralasciando il linguaggio di programmazione (di cui ho conoscenze appena di base, acquisite durante un corso universitario) che uso, mi interesserebbe soprattutto capire il tipo di struttura dati migliore da utilizzare e come utilizzarla, in particolare:

- come faccio ad implementare un grafo? (nodi, archi...)
- come faccio ad inizializzare un grafo casuale formato da n nodi?
ad esempio quando avvio il programma, inizializzo il mio grafo con, per esempio, 10 nodi, ma poi come faccio a realizzare i collegamenti tra nodi in maniera casuale senza che sia io a realizzare i collegamenti ogni volta che avvio il mio programma?

Grazie in anticipo per le risposte!

[Floris]

Solitamente per implementare un grafo diretto con n nodi conviene implementare una matrice binaria nxn dove 1 nella posizione i,j significa che vi è un arco dal nodo i al nodo j (se il grfo non è diretto la matrice è simmetrica).
A questo punto crei gli archi casualmente tramite una funzione randomizzante in due modi:
- o per ogni casella della matrice produci randomicamente un intero in {0,1}
- oppure se vuoi m archi produci randomicamente m coppie (i,j) di numeri interi in [0,n).

[Jim Stacey]

Grazie per la dritta...in pratica è una matrice di adiacenza...! Esiste una libreria in Java per realizzare Grafi?

[banryu79]

Originariamente inviato da Jim Stacey

Grazie per la dritta...in pratica è una matrice di adiacenza...! Esiste una libreria in Java per realizzare Grafi?

JGraphT per le strutture dati e gli algoritmi.
JGraph invece se ti serve anche visualizzare i grafi in componenti grafici Swing.
(oppure, in questo secondo caso, usi JGraphT e i suoi wrapper per JGraph).