Algoritmo di percorso più breve di Dijkstra con costo del fronte

Ho un grafico ponderato positivo diretto. Ogni bordo ha un costo di utilizzo. Ho solo un denaro, voglio calcolare i percorsi più brevi con l'algoritmo dijkstra, ma la somma dei costi dei bordi sul percorso deve essere inferiore o uguale a A.Algoritmo di percorso più breve di Dijkstra con costo del fronte

Voglio fare questo con la modifica Dijstra più piccola (se posso fallo con piccole modifiche di Dijkstra). Devo farlo in O(n*log(n)) se posso, ma penso di poterlo fare.

Chiunque può aiutarmi con questo?

fonte

2010-04-26 Svisstack

Come al solito con le domande dei compiti a casa - cos'hai fino ad ora? – Stephen

Sto capendo correttamente il problema: ogni spigolo ha una lunghezza e un costo, e tu vuoi minimizzare la lunghezza con il vincolo in più che il costo deve essere inferiore o uguale a A. –

@Mark Byers: Sì, voglio fare il percorso più breve con questo vincolo extra per ogni percorso deve essere vero. – Svisstack

https://www.spoj.pl/problems/ROADS/

Il problema è stato dato a CEOI '98 e la sua soluzione ufficiale si possono trovare here.

fonte

2010-04-28 05:42:49 IVlad

Forse mi manca qualcosa qui, ma nessuno di questi collegamenti presenta in realtà un algoritmo che risolve questo problema. Gli invii SPOJ contengono algoritmi, ma non possiamo leggere il codice sorgente per loro! –

In realtà non è necessario modificare l'algoritmo di Dijkstra per fare questo come la risposta è equivalente a trovare il percorso più breve e quindi accettarla se è inferiore o uguale ad A.

Naturalmente, si può sempre cortocircuiti il ciclo interno se visiti un percorso con un costo superiore a A.

MODIFICA: Con la precisazione che desideri ridurre al minimo il costo E la distanza, non puoi farlo senza chiarire la soluzione che desideri. Vuoi il percorso più economico? Vuoi il percorso più breve? Vuoi una qualche funzione di costo e distanza? Tutti questi determinano quale funzione di ponderazione si dovrebbe usare per un particolare bordo.

fonte

2010-04-26 01:05:45 MSN

Il costo e la lunghezza di un bordo sono due cose diverse, controlla i commenti. – michalburger1

@Bus Non ha detto nulla di una lunghezza nella sua domanda. Per quanto ne so, l'unico valore associato a ogni spigolo è il costo. – Enrique

Quale dei molti significati che Svisstack intendeva non è ancora chiaro neanche a me, anche dopo aver risposto alla domanda di Mark. – outis

Algoritmo di percorso più breve di Dijkstra con costo del fronte

risposta

Problemi correlati