Existe-t-il un algorithme optimal pour trouver le chemin le plus long et le plus court dans un réseau?

13

J'ai un grand ensemble de réseaux linéaires et je voudrais trouver les deux extrémités de chaque réseau qui sont les plus éloignées l'une de l'autre le long du réseau (sur l'image ci-dessous, ce serait D à K). La solution par force brute à ce problème est de calculer le chemin le plus court le long du réseau pour chaque paire d'origine, mais j'ai des centaines de réseaux avec des milliers d'extrémités, donc le calcul de chaque chemin possible est assez lourd.

Existe-t-il un moyen optimal de calculer cela sans utiliser la force brute? Puis-je exclure certains points en fonction de règles intelligentes?

Comment trouver efficacement le chemin rouge?

EDIT: J'ai ajouté une illustration du plus long chemin mentionné par @Alex Tereshenkov afin de clarifier ma question. Le chemin noir est le résultat de l'algorithme du chemin le plus long (le chemin le plus long sans répéter aucun sommet). Dans mon cas, imaginez que vous entrez dans le réseau à partir de l'une des lettres et que vous devez conduire vers une autre lettre aussi vite que possible. Quelles sont les deux lettres les plus difficiles à joindre? entrez la description de l'image ici

radouxju
la source
compétences de peinture folle!
Adam

Réponses:

6

Je pense que vous cherchez peut-être le diamètre du graphique de votre réseau. Il y a quelques questions sur stackexchange qui mentionnent ce sujet, par exemple:

La plupart des algorithmes suggèrent de calculer d'abord les "chemins les plus courts toutes paires" et de sélectionner les plus longs, mais j'ai trouvé un article de blog de Koushik Narayanan qui suggère une approche alternative qui pourrait être plus optimale (je n'ai pas vérifié), qui itère sur chaque sommet et trouve sa paire la plus éloignée:

Nous pouvons calculer le chemin à partir d'un sommet V1 de sorte qu'il soit le chemin le plus court entre V1 et l'un des sommets et qu'il soit plus long que le chemin le plus court entre tout autre sommet. Voir cet article pour un algorithme. Ensuite, nous pouvons parcourir chaque sommet et trouver le chemin le plus long avec chaque sommet comme racine. Une fois que nous avons la liste de tous les chemins les plus courts, nous pouvons trouver celui qui a la valeur maximale et la renvoyer.

mkadunc
la source
merci, le diamètre du graphique était exactement ce que je cherchais, et l'heuristique pseudo-diamtre fonctionne dans mon cas. Je viens d'apprendre de nouveaux mots là-bas!
radouxju
7

Selon la page Wikipedia Problème de chemin le plus long , ce problème

... est NP-difficile, ce qui signifie qu'il ne peut pas être résolu en temps polynomial pour des graphes arbitraires à moins que P = NP. Des résultats de dureté plus élevés sont également connus, ce qui montre qu'il est difficile à estimer. Cependant, il a une solution temporelle linéaire pour les graphiques acycliques dirigés, qui a des applications importantes pour trouver le chemin critique des problèmes de planification.

Si vous travaillez avec (ou pouvez représenter votre graphique comme DAG ), le networkxpackage Python vous permettra de le calculer. Recherchez la fonction dag_longest_path.

À moins que je manque quelque chose, vous devrez calculer la longueur entre les nœuds du graphe et les trier, ce qui, malheureusement, ne fonctionnera qu'en temps linéaire , c'est-à-dire qu'il n'y a pas d' algorithme efficace pour cela.

Alex Tereshenkov
la source
merci pour la réponse, déjà + 1 à cause de l'information. Cependant, je recherche le plus long DU CHEMIN LE PLUS COURT dans un réseau (dans mon exemple, pas de détour vers B ou H). Par conséquent, votre solution n'est pas exactement ce que je recherche, même si elle laisse entendre que la «force brute» est probablement la seule solution.
radouxju
@radouxju, ah je vois. Eh bien, voyons si le gène le remarquera, il a beaucoup d'expérience avec les graphiques, peut-être qu'il a des idées brillantes.
Alex Tereshenkov