Dato un grafo non orientato ponderato G e due nodi U, V per ottenere il percorso più breve. Come posso ottenere il percorso più breve da U a V che utilizza un numero pari di spigoli (se possibile per ottenerlo)?Percorso più breve con numero pari di spigoli
Ho trovato alcuni articoli sul web che dicono che è necessaria una modifica sul grafico originale. Ma non riesco a capire come farlo.
C'è qualche buon materiale da studiare su questo problema?
Avrete bisogno di costruire un grafico intermedio ed eseguire Dijkstra su quel grafico.
Dato un grafo G = (V, E), creare un nuovo grafico G' = (V', E'), con V' un nuovo insieme di vertici v_even e v_odd per ogni vertice v in V e E' l'insieme di vertici come segue: Se (u, v) è un vantaggio in G, allora (u_odd, v_even) e (u_even, v_odd) sono spigoli in G', con lo stesso peso.
Ovviamente, il nuovo grafico ha il doppio dei bordi e dei vertici del grafico originale.
Ora, se si voleva trovare il percorso più breve tra s e t in G, basta eseguire Dijkstra di su G' per trovare il percorso più breve tra s_even e t_even.
Il tempo di esecuzione è ancora O(|V| log |E|).
Questo ti darà la camminata anche più breve, non il percorso più corto. Anche se ciò che si trova usando l'algoritmo di Dijkstra è un percorso, quando si uniscono i bordi "gemelli", potrebbe diventare una scia o addirittura una passeggiata. Come controesempio, prendi il grafico ottenuto dall'unione disgiunta di un triangolo e un percorso di lunghezza 3, e quindi identifica un vertice di triangolo con un vertice interno del percorso. – Untitled
@Un titolo se capisco correttamente la tua argomentazione: il mio approccio non è corretto perché un modo per trasformare una camminata di lunghezza dispari in una camminata di lunghezza pari consiste nel fare un giro completo su un ciclo di lunghezza dispari. Hai ragione, questo è un valido contro esempio che questo approccio non funziona in generale. –
Che dire di eseguire Dijkstra in cui ogni nodo ha due valori. Uno è strano (proveniente da un valore pari) e l'altro è pari valore.
Dijkstra's è un algoritmo avido. Non è possibile memorizzare entrambi i valori nello stesso nodo perché verrà visitato solo una volta e il valore pari potrebbe essere molto diverso dal valore dispari. –
In alternativa, è possibile creare un nuovo grafico con due tipi di nodi in cui è possibile che ogni nodo dispari punti a nodo pari e viceversa. In questo modo non si modifica Dijkstra (stavo pensando) ma grafico. –
Questo ti darà una passeggiata, non un percorso. Per favore, vedi il mio commento sulla risposta di Vincent. – Untitled
Tale percorso deve avere come uno dei suoi punti finali e copia di v come l'altro endpoint, poiché sono gli unici vertici scoperti. Se si uniscono le copie e si eliminano i bordi aggiunti, il percorso trovato corrisponde a un percorso uniforme, poiché inizia da una copia e termina su un'altra. Inoltre, ogni percorso pari corrisponde a un percorso aumentante (per lo stesso argomento), quindi il minimo di uno è anche il minimo dell'altro. Questo è spiegato in here.
Puoi postare un link su un documento liberamente accessibile? –
@LukaRahne Scusa Luka. Non sono riuscito a trovarne uno. Immagino che se chiedi agli autori ti concederebbero l'accesso. Forse prova a richiederli attraverso la pagina ResearchGate di questo articolo. – Untitled
Questa domanda si adatterebbe meglio nello stack di informatica. – Untitled