[JAVA - Algoritmi di cammino minimo su Grafi non orientati]

[DeltaDirac]

Sono ben note le implementazioni degli algoritmi di Dijkstra, Bellman-Ford ecc su GRAFI ORIENTATI per la ricerca del percorso a costo minimo, mentre non riesco a trovare un algoritmo altrettanto testato applicabile ad un Grafo non orientato.

Ho una rete a disposizione di cui vorrei implementarne il Grafo che, data la tipologia, vorrei fosse di tipo non orientato.

Volendo evitare trasformazioni da Grafo Non Orientato --> Grafo Orientato per poter usare Dijkstra & C, mi chiedo: esistono altre soluzioni? Se si, quali?


Grazie

[Don[ITA]]

Prova a dare un'occhiata agli algoritmi di Prim e Kruskal

[tuccio`]

ma li puoi usare entrambi su grafi semplici, comunque un'immagine vale più di mille parole

[oNaSsIs]

tuccio ha ragione. Piuttosto devi assicurarti che gli archi abbiano tutti un peso non negativo.

[DeltaDirac]

Ciao a tutti e grazie per le risposte.

Dunque: sicuramente non esistono archi con pesi negativi perché i pesi sono distanze fisiche, e questo semplifica di sicuro il problema. Circa la semplicità di cui parla tuccio, non ho le idee chiare: il Grafo contro cui sto combattendo ha una cinquantina di nodi e un centinaio di archi (a spanne).

Stavo leggendomi la documentazione dei due algoritmi mi pare di capire che (correggetemi se sbaglio):

- Prim si realizza con strutture dati di tipo liste di adiacenza / code di priorità (risp. Grafo e dati aux) ed ha una complessità O(m log(n)) sempre

- Kruskal ha complessità O(m log(n)) se realizzato con struttire dati di tipo union-find, altrimenti O(mn) in tutti gli altri casi

C'è qualche altra considerazione che potrebbe aiutarmi a spostare la preferenza verso uno dei due?

[tuccio`]

prim e kruskal calcolano il minimum spanning tree, non il cammino minimo

[DeltaDirac]

Ecco, io cercavo proprio un algoritmo per determinare il cammino minimo nei grafi non orientati, preferibilmente in Java

[british]

Originariamente inviato da DeltaDirac

Ecco, io cercavo proprio un algoritmo per determinare il cammino minimo nei grafi non orientati, preferibilmente in Java

Appunto, puoi usare Dijkstra (o Bellman-Ford, o Floyd-Warshall). Gli archi del tuo grafo non orientato corrispondono a doppi archi ("andata + ritorno") in uno orientato.

ciao!

british

[DeltaDirac]

Originariamente inviato da british

Appunto, puoi usare Dijkstra (o Bellman-Ford, o Floyd-Warshall). Gli archi del tuo grafo non orientato corrispondono a doppi archi ("andata + ritorno") in uno orientato.

ciao!

british

Quindi tu stai dicendo che potrei trasformare il grafo NO in un grafo O raddoppiando il numero di archi (e quindi lo spazio occupato) e poi applicare Dijkstra?

Proprio non esiste algoritmo testato per determinare un cammino minimo in un Grafo NO?

Giusto per capire bene i termini della questione.

[tuccio`]

ora che ci penso, se trasformi un grafo orientato in quel modo si formano cicli negativi per ogni arco con peso negativo, quindi boh, Bellman-Ford non sono sicuro tu possa utilizzarlo sui grafi semplici facendo questo lavoro qui

[DeltaDirac]

Originariamente inviato da tuccio`

ora che ci penso, se trasformi un grafo orientato in quel modo si formano cicli negativi per ogni arco con peso negativo, quindi boh, Bellman-Ford non sono sicuro tu possa utilizzarlo sui grafi semplici facendo questo lavoro qui

Ma io non ho archi con pesi negativi, derivando, come detto all'inizio, da una misura fisica (metri).

Piuttosto mi chiedo se non faccio prima a costruirmi un algoritmo di visita personalizzato e poi da questo ricavarne il percorso minimo.

Se solo esistesse un algoritmo di cammino minimo su Grafi non orientati già pronto e testato, sarebbe tutto più facile!

[banryu79]

Ecco, io cercavo proprio un algoritmo per determinare il cammino minimo nei grafi non orientati, preferibilmente in Java
...
Se solo esistesse un algoritmo di cammino minimo su Grafi non orientati già pronto e testato, sarebbe tutto più facile!

Ciao, in Java esiste la libreria JGraphT, la trovi qui. Devi studiartela un'attimo, consulta i tutorial e spendi un po' di tempo a fare piccole prove e leggere i javadoc (poca roba tutto sommato).

In particolare credo che questo sia quello che stai cercando (il fatto che l'algoritmo accetti come argomento l'interfaccia Graph significa che lo si può far operare su qualsiasi sua implementazione, ad esempio su un UndirectedGraph, che è poi la rappresentazione di un genrico grafo non orientato in JGraphT).

Piuttosto mi chiedo se non faccio prima a costruirmi un algoritmo di visita personalizzato e poi da questo ricavarne il percorso minimo.

Probabilmente non ti serve, ma in caso sappi che con JGraphT l'implentazione di algoritmi di visita personalizzati è supportata mediante il Visitor Pattern.

[british]

Originariamente inviato da DeltaDirac

Quindi tu stai dicendo che potrei trasformare il grafo NO in un grafo O raddoppiando il numero di archi (e quindi lo spazio occupato) e poi applicare Dijkstra?

e perchè no?
e l'aumento eventuale di spazio dipende da come è implementato il grafo (matrice/lista di adiacenze/insiemi di adiacenze)

ciao!

british

[oNaSsIs]

Originariamente inviato da DeltaDirac

Ma io non ho archi con pesi negativi, derivando, come detto all'inizio, da una misura fisica (metri).

Piuttosto mi chiedo se non faccio prima a costruirmi un algoritmo di visita personalizzato e poi da questo ricavarne il percorso minimo.

Se solo esistesse un algoritmo di cammino minimo su Grafi non orientati già pronto e testato, sarebbe tutto più facile!

Scusa ma forse mi sfugge qualche dettaglio, perchè gli algoritmi già proposti di Dijkstra, Bellman-Ford, Floyd-Warshall (che funzionano indipendentemente dal fatto che il grafo sia orientato oppure no) non risolvono il tuo problema?

[DeltaDirac]

Vorrei ringraziare tutti per gli interessanti spunti che mi avete offerto con le vostre osservazioni.

Considerando che devo lavorare con un Grafo aciclico non orientato con pesi tutti positivi, posso effettivamente applicare un algoritmo a scelta tra Floyd-Warshall, Dijkstra e Bellman-Ford.

Poiché dovrò (almeno inizialmente) calcolare cammini minimi a sorgente singola, scarterei a priori Floyd-Warshall in favore di Dijkstra e Bellman-Ford; si tratta adesso di stabilire quale sia più efficiente e con quali strutture dati vanno realizzati.

Se ho ben capito, Dijkstra offre una prestazione sul tempo totale O(m + n log n) mentre Bellman-Ford offre O(nm), rendendo il primo vincente sul secondo.

Venendo al grafo vero e proprio, più o meno è fatto così:

Node1 Node2 dist12 Node3 dist13 Node5 dist15
Node2 Node3 dist23 Node4 dist24
Node3 Node5 dist35
...

Dove, per ogni Nodo presente in colonna 1, seguono i Nodi connessi e i pesi (non negativi) associati ai relativi archi.

Quale struttura dati sarebbe consigliabile implementare per rendere efficiente Dijkstra?

[tuccio`]

Originariamente inviato da DeltaDirac

Ma io non ho archi con pesi negativi, derivando, come detto all'inizio, da una misura fisica (metri).

Piuttosto mi chiedo se non faccio prima a costruirmi un algoritmo di visita personalizzato e poi da questo ricavarne il percorso minimo.

Se solo esistesse un algoritmo di cammino minimo su Grafi non orientati già pronto e testato, sarebbe tutto più facile!

sì sì, ma come ti ho detto, dijkstra lo puoi applicare anche su grafi semplici.. bellman ford in generale no probabilmente (puoi se hai la garanzia che i pesi siano tutti positivi, ma a questo punto usi dijkstra che ha minore complessità)

Originariamente inviato da DeltaDirac

Quale struttura dati sarebbe consigliabile implementare per rendere efficiente Dijkstra?

fibonacci heap per O(m+nlogn)

[DeltaDirac]

Grazie Tuccio!

Vado di Dijkstra e tento l'implementazione attraverso l'heap di Fibonacci.
Sicuramente mi farò vivo di nuovo