Référence pour un algorithme rapide pour les chemins les plus courts

12

Je suis à la recherche d'une bonne référence pour les plus courts chemins de goulot d'étranglement. Plus précisément, étant donné les sommets s et t dans un graphique non orienté avec des poids de bord, vous voulez le chemin le plus court de s à t, où la longueur d'un chemin est le bord maximum sur ce chemin. Cela peut être résolu en temps O (n + m) en trouvant le poids médian des bords et en supprimant (soigneusement) récursivement la moitié des bords.

Quelqu'un connaît-il une référence pour cela?

ds.algorithms reference-request graph-algorithms Ben
la source
C'est peut-être un point discutable, mais le problème que vous décrivez est le problème du chemin minimax. Le chemin le plus court du goulot d'étranglement est la version max-min de ce que vous décrivez. Un algorithme pour l'une des versions donne généralement (toujours?) Un algorithme pour l'autre version cependant.
bbejot

Réponses:

10

PM Camerini (1978), The min-max spanning tree problem and some extensions, Information Processing Letters 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
la source
5
Btw, si vous voulez résoudre la version à source unique (et dans un sens toutes les paires) du problème pour les graphiques non dirigés, vous pouvez le faire en temps O (m + n) aléatoire: TC Hu a noté en 1961 que le les chemins de goulot d'étranglement pour toutes les paires sont codés dans un arbre couvrant maximum; alors l'algorithme d'arbre couvrant le temps linéaire min de Karger, Klein et Tarjan vous donne ce que vous voulez.
virgi
Pour autant que je sache, la référence n'est pas ce dont j'ai besoin. Un chemin st dans un arbre couvrant min-max n'est pas nécessairement un chemin st le plus court du goulot d'étranglement. De plus, l'algorithme de temps prévu linéaire KKT n'est pas non plus ce dont j'ai besoin, car je veux un temps d'exécution déterministe non attendu. Merci quand même pour l'aide.
Ben
4
En fait, le chemin st P dans un arbre couvrant minimum T a un poids de bord maximum minimum sur tous les chemins st. Supposons que ce ne soit pas le cas. Soit alors le bord max de P soit e. La suppression de e de T crée une coupe du graphique. Le vrai chemin minmax st P 'doit avoir une arête e' traversant cette coupe. L'ajout de e 'à T \ {e} crée un nouvel arbre couvrant T' qui doit avoir un coût inférieur à T puisque le poids de e 'est tout au plus le poids de bord maximum sur P' qui est inférieur à w (e). Cela contredit le fait que T est un arbre couvrant min.
virgi