Dijkstra algorithme de chemin le plus court avec un coût de bord

Question

J'ai un graphique pondéré réalisé, positif. Chaque bord ont un coût d'utilisation. Je n'ai que l'argent, je veux calculer les plus courts chemins avec l'algorithme de Dijkstra, mais somme des coûts des bords sur la route doit être inférieure ou égale à A.

Je veux le faire avec la plus petite modification Dijstra (si je peux le faire avec une petite modification de Dijkstra). Je dois le faire en O(n*log(n)) si je peux, mais je pense que je peux.

Tout le monde peut me aider?

Answer 1

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

Le problème a été donné à et '98 IET sa solution officielle peut être trouvée ici .

Answer 2

Vous n'avez pas vraiment besoin de modifier l'algorithme de Dijkstra pour ce faire que la réponse équivaut à trouver le chemin le plus court, puis l'accepter si elle est inférieure ou égale à A.

Bien sûr, vous pouvez toujours court-circuiter la boucle interne si vous visitez un chemin avec un coût plus A.

EDIT: Avec la précision que vous voulez réduire le coût et la distance, vous ne pouvez pas faire cela sans préciser la solution que vous voulez. Voulez-vous le moins cher chemin? Voulez-vous le plus court chemin? Voulez-vous une fonction du coût et de la distance? Tous ces éléments déterminent quelle fonction de pondération, vous devez utiliser un bord particulier.