Se si dispone di un grafico non orientato ponderato senza pesi negativi, ma può contenere più spigoli tra vertici e loop automatici, È possibile eseguire l'algoritmo Dijkstra senza problemi per trovare il percorso minimo tra una fonte e una destinazione o esiste un controesempio? 
Dijkstra con bordi paralleli e self-loop
La mia ipotesi è che non ci siano problemi, ma voglio essere sicuro.
Se stai per eseguire l'algoritmo di Dijkstra senza apportare modifiche al grafico, c'è la possibilità che tu sia non ottenere il percorso più breve tra origine e destinazione.
Ad esempio, considerare S e O. Ora, la ricerca del percorso più breve dipende proprio da quale bordo viene attraversato quando si desidera inviare O alla coda. Se il tuo codice prende vantaggio con il peso 1, stai bene. Ma se il tuo codice sceglie il vantaggio con il peso 8, allora il tuo algoritmo ti darà la risposta sbagliata.
Ciò significa che la correttezza dell'algoritmo dipende ora dall'ordine dei bordi immesso nell'elenco di adiacenze del nodo di origine.
Ciò che è importante è che se funzionerà o meno non è una proprietà dell'algoritmo, è la proprietà dell'implementazione. – biziclop
È possibile trasformare banalmente il proprio grafico in uno senza loop con bordi singoli e bordi paralleli.
Con loop single-edge è necessario verificare se il loro peso è negativo o non negativo. Se il peso è negativo, ovviamente non esiste un percorso più breve, poiché è possibile continuare a ruotare e ridurre la lunghezza del percorso oltre ogni limite. Se tuttavia il peso è positivo, puoi gettare via quel bordo, poiché nessun percorso più breve può attraversare quel bordo.
Un margine di peso zero creerebbe un problema simile a qualsiasi altro ciclo di peso zero: non ci sarà uno, ma un numero infinito di percorsi più brevi, che attraversano lo stesso ciclo più e più volte. In questi casi la cosa sensata è di nuovo di rimuovere il bordo dal grafico.
Fuori dai bordi paralleli è possibile gettare via tutti tranne uno con il peso più basso. Il ragionamento per questo è altrettanto semplice: se c'è un percorso più breve che attraversa un bordo A con un margine parallelo B con un peso inferiore, è possibile costruire un percorso ancora più breve semplicemente sostituendo A con B. Pertanto, nessun percorso più breve può passare attraverso A.
Ok, sembra fantastico. Ma la mia domanda è: se eseguo Dijkstra Algorithm su quel grafico senza alcuna modifica, potrebbe esserci un problema? – Manuel
@Manuel Questo dipende completamente dall'implementazione. Ad esempio, nel passaggio che calcoli la distanza dal nodo 'N' a tutti i suoi vicini, un'implementazione potrebbe assumere che ogni fronte uscente da' N' porta a un nodo diverso, quindi potrebbe memorizzare il risultato in una mappa in cui i nodi sono le chiavi. In quel caso i bordi paralleli possono facilmente portare al risultato sbagliato. – biziclop
Ha solo bisogno di una variazione minore. Se ci sono più archi orientati da u a v e ogni bordo ha un peso diverso, è possibile:
Entrambe le suddette avranno la stessa complessità anche se i fattori costanti in # 2 avranno valori più alti.
In ogni caso è necessario assicurarsi di valutare tutti i bordi tra u e v prima di passare al successivo nodo adiacente di u.
Come le risposte citate, dipende molto dalla particolare implementazione dell'algoritmo dijkstra. [Questo] (https: //www.quora.com/What-is-the-most-simple-efficient-C% 2B% 2B-code-per-Dijkstras-shortest-path-algorithm/answer/Michal-Fori% C5% A1ek? srid = ojqI) l'implementazione funzionerà bene perché aggiunge il bordo più piccolo possibile tra tutti i possibili bordi paralleli alla struttura dati che si sta utilizzando per tenere traccia dei nodi ancora da esplorare. – thebenman