Pouvons-nous trouver k les chemins les plus courts entre toutes les paires plus rapidement que de résoudre le problème par paire à plusieurs reprises?

9

Je veux produire chemin le plus court ( k serait inférieur à 10) entre toutes les paires dans un graphique. Le graphique est (en fait une carte de métro):kk

  • pondéré positivement
  • non dirigé
  • clairsemé
  • avec environ 100 nœuds

Mon plan actuel consiste à appliquer routage de chemin le plus courtk à chaque paire; Je cherche maintenant une alternative plus efficace (éventuellement avec une programmation dynamique).

algorithms graphs optimization shortest-path Franklin Yu
la source
3
Honnêtement, pour 100 sommets, il semble peu probable que vous ayez besoin de quelque chose de plus efficace que de résoudre chacun des 45 000 problèmes par paire.
David Richerby

Réponses:

6

k

k

Cela semble être un domaine de recherche assez récent. Un article récent d'Agarwal et Ramachandran peut être trouvé sur l'ArXiv [1]. La section des travaux précédents vous donnera également un aperçu de l'historique du problème.

Le toutes pairesk

Ici, en effet, c'est le meilleur choix pour appliquer simplement à plusieurs reprises l'algorithme Eppsteins [2]. L'observation générale qu'une application répétée d'un algorithme pour la version à source unique du problème est l'approche la plus rapide a déjà été faite en 1977 par EL Lawler [3]; Eppstein fournit l'algorithme le plus rapide à ce jour pour ce sous-problème.

Références

k

[2] Eppstein, D. Trouver les k chemins les plus courts. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, EL Commentaire sur un calcul des k chemins les plus courts dans un graphe. Communications de l'ACM, 20 (8): 603–605, 1977.

Mensonge
la source
Je vous remercie. Étant donné que je travaille avec une carte de métro, j'ai besoin qu'ils soient un chemin simple (cela n'a pas de sens pour mon logiciel de guider les gens dans les deux sens), donc je suppose que j'irais avec l'algorithme de Yan .
Franklin Yu
Intéressant et assez surprenant que, apparemment, 10 000 cas d'un problème ne peuvent pas être résolus plus rapidement que de résoudre 10 000 cas individuels, l'un après l'autre.
gnasher729
l'idée de chemins avec des boucles incluses dans les "chemins les plus courts" semble contre-intuitive et inhabituelle car il y a apparemment un "chemin" équivalent avec la boucle supprimée, et on se demande également si ceux-ci peuvent être construits efficacement à partir des chemins simples etc ...
vzn