L'algorithme de plus court chemin de Dijkstra ne fonctionnera pas

J'ai un graphique avec des poids de bord positifs et des poids de nœuds positifs. La longueur d'un chemin est définie comme la somme de tous les poids de bord le long du chemin, plus le poids maximum du nœud rencontré le long du chemin.L'algorithme de plus court chemin de Dijkstra ne fonctionnera pas

Je pensais initialement qu'un Dijkstra modifié fonctionnerait, mais j'ai trouvé un cas de test où il échouerait. Comment devrais-je résoudre ce problème? Y a-t-il des algorithmes standard que je devrais regarder? Ma Dijkstra modifiée est la suivante: À chaque nœud, j'enregistre le chemin le plus court jusqu'à présent, ainsi que le poids de nœud maximum que j'ai vu jusqu'ici, et je l'utilise pour calculer la longueur des nœuds voisins. S'il vous plaît voir mon commentaire pour les détails.

est ici un graphique où Dijkstra échoue: http://i.imgur.com/FQhRzXV.jpg Les chiffres en vert sont les étiquettes de nœud. Tout en bleu est des poids (poids de nœud et de bord). Disons que je veux calculer le chemin le plus court entre les nœuds 1 et 7 (marqué en vert). Le problème avec Dijkstra est que le noeud 4 enregistre toujours le chemin 1-8-9-4 puisque son plus court que le chemin 1-2-3-4 (ancienne longueur 9 vs dernière longueur 13). Mais pour atteindre le nœud 7, le chemin 1-8-9-4-5-6-7 est plus long que 1-2-3-4-5-6-7.

Source

2013-09-21 elexhobby

Qu'avez-vous essayé et pourquoi a-t-il échoué? Je suis assez sûr qu'un Dijkstra modifié fonctionnerait :-) –

Fixer le noeud de début. Pour chacun de ses voisins, stockez une paire de nombres - (le chemin le plus court vers ce voisin, le poids de nœud maximum rencontré jusqu'à présent sur le chemin d'accès à ce nœud). Mettez-les dans une file d'attente et choisissez le noeud ayant le chemin le plus court. Continuer. Lors de l'ajout d'un nouveau nœud b connecté à un nœud visité a, si le poids de b elexhobby

Je pense que vous avez résolu "chemin avec le poids total minimum, plus garder la trace du plus grand bord pondéré sur ce chemin." Je pense que le problème est probablement de demander "chemin avec le minimum (poids total plus le poids le plus important)". Le simple suivi du plus gros poids ne résoudra pas cela. – DanielV

Si vous pouvez pardonner un ordre plus grand polynomiale, alors algorithme assez facile:

ModifiedShortestPath(u, v, G) { 
    X = StandardardShorestPath(u, v, G); 
    E = heaviest edge in X 
    F = all edges in G of weight >= E 
    Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges 
    return Min(X, Y); 
}

L'exécution de c'est | E | fois plus que votre chemin le plus court standard.

Source

2013-09-21 20:08:57 DanielV

L'algorithme de plus court chemin de Dijkstra ne fonctionnera pas

Répondre

Questions connexes