L'algoritmo di Dijkstra è per i grafici diretti o indiretti?

Question

Continuo a provare a google, ma i risultati che sto riscontrando stanno solo aggiungendo alla mia confusione. Sembra che possa essere eventualmente usato per entrambi? In tal caso, per quale motivo è stato progettato per impostazione predefinita e cosa è necessario modificare per farlo funzionare in modo non predefinito (indipendentemente dal fatto che sia diretto o non diretto)?

Edit: per riferimento, ho avuto un problema lo scorso semestre in cui mi è stata data una lista come questa (aeroporti):

AER,KZN,1.8835 
ASF,KZN,1.3005 
ASF,MRV,1.1204 
CEK,KZN,1.9263 
CEK,OVB,1.6733 
DME,KZN,1.7892 
DME,NBC,2.2319 
DME,UUA,2.3786 
EGO,KGD,1.4649 
EGO,KZN,1.2603 
GYD,NBC,2.0755 

mi hanno detto che era diretto, e ha chiesto di trovare il percorso più breve. L'ho inserito nell'algoritmo di Dijkstra che ho trovato su Github (era un midterm open-computer, quindi non avevamo abbastanza tempo per scrivere l'algoritmo da zero) e il mio professore ha detto che il percorso più breve che ha restituito non era corretto e che era nemmeno un possibile percorso perché la lista doveva essere diretta. Non ero sicuro di dover modificare l'algoritmo o l'elenco per effettuare questa correzione. Finì per essere il caso in cui il secondo percorso più breve che è stato restituito fosse in realtà il percorso più breve diretto, ma mi chiedo ancora quale fosse il problema.

Answer 1

Può essere applicato a entrambi. Ecco perché:

un grafo non orientato è fondamentalmente lo stesso di un diretto grafico con bidirezionali connessioni (= due connessioni in direzioni opposte) tra i nodi collegati.

Quindi non devi fare nulla per farlo funzionare per un grafico non orientato. Hai solo bisogno di conoscere tutti i nodi che possono essere raggiunti da ogni nodo dato attraverso ad es. un elenco di adiacenza .

Answer 2

Un grafico diretto indica che i bordi che collegano i vertici sono in grado di connettersi in un modo, ma non nell'altro. Ciò significa che un vertice può essere adiacente ad un altro, ma che l'altro vertice potrebbe non essere adiacente al primo vertice.

Nel contesto dell'algoritmo di Dijkstra, non importa se il grafico è diretto o non orientato. L'algoritmo di Dijkstra fa semplicemente riferimento ai vertici adiacenti di un vertice. È questa lista di adiacenze che dovresti modificare se stavi cambiando un grafico da diretto a non orientato.

Answer 3

L'algoritmo di Djikstras è in genere per Grafici pesati positivi. Forse lo stai confondendo con l'algoritmo di ampiezza della prima ricerca (BFS), che è essenzialmente Djikstras per i grafici non pesati. La differenza (tra Djikstras e BFS), è quando si hanno a che fare con percorsi ponderati, ora dobbiamo considerare le rettifiche dei costi di percorso (pesi) & le decisioni su quali nodi visitare dopo la corrente.

Answer 4

È possibile utilizzare l'algoritmo di Dijkstra in entrambi i grafici diretti e non orientati, poiché si aggiungono semplicemente spigoli in PriorityQueue quando si dispone di un margine per raggiungere il proprio elenco di adiacenze. Ad esempio, se uno dei miei nodi ha un margine da A a B di peso 3, se è diretto da BI non sarà in grado di aggiungere il bordo in A, mentre da AI potrebbe aggiungerlo a B.

Come le altre risposte, assicurati di non confonderla con i pesi. L'algoritmo di Dijkstra funziona su grafici positivi pesati, altrimenti la coda di priorità sarebbe inutile.

Nel tuo esempio, l'algoritmo di Dijkstra funzionerebbe perché il grafico è pesato (positivamente) e ha i bordi diretti.

L'errore sarebbe stato che i bordi sono stati assegnati due volte sotto forma di un grafico non orientato. Si dovrebbe fare attenzione quando si analizzano i bordi all'inizio degli oggetti per non duplicare i bordi nell'elenco di adiacenza.