Question de la théorie des graphes, Java. Quel algorithme pour atteindre les objectifs suivants

Question

J'ai un graphe, avec X nœuds et Y bords. Bords lestés. Le point est de commencer à un noeud et d’arrêter à un autre. Maintenant, voici le problème;

Visualisez le problème. Les bords sont des routes et les poids des bords sont les limites maximales de poids pour les véhicules circulant sur les routes. Nous aimerions conduire le plus gros camion possible de A à B. Ainsi, le poids maximum autorisé pour un camion empruntant un chemin donné est le plus petit poids de tous les bords dans ce chemin. Je veux le plus grand poids maximum autorisé pour tous les chemins de A à B.

Puis-je utiliser une sorte d'algorithme de Dijkstra pour résoudre ce problème? Je ne sais pas comment exprimer ce problème sous la forme d'un algorithme que je peux implémenter. Toute aide est très appréciée.

Mise à jour: J'ai testé des choses qui ne fonctionnaient pas pour moi. Un nœud devrait avoir un camion max pour chaque bord entrant.

Answer 1

L'algorithme de

Dijkstra devrait fonctionner, mais votre " distance " dans ce cas, c'est un peu bizarre. Votre & Quot; distance & Quot; est le camion de taille maximale que vous pouvez obtenir à un nœud. Appelons cela M [v] pour un nœud v. Vous devez traiter les nœuds dans l'ordre, du plus grand M [v] au plus petit M [v] (contrairement à la normale Dijkstra), et calculer pour chaque arête e de v à w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

Cela ressemble (presque) exactement au problème de débit maximal qui peut être résolu efficacement à l'aide de algorithme de Ford-Fulkerson .

Comme Keith l’a souligné dans un commentaire, l’algorithme doit être légèrement modifié pour ne trouver que un chemin avec un segment de chemin minimal maximisé, car le camion ne peut & # 8217; t être divisé en plusieurs parties.

Answer 3

Je pense que vous cherchez ceci

chemin le plus court

modifier: en fait, vous n'êtes pas absent et le lien de flux maximal est correct

Answer 4

Donc, si je comprends bien, vous demandez & "Quel est le plus gros camion pouvant conduire de A à B &";

Pour appliquer l'algorithme de Dijkstra, vous aurez besoin d'un moyen de modéliser & "coût &"; Si vous souhaitez utiliser une implémentation standard, vous pouvez affecter l'inverse du poids au coût. Ainsi, l’avantage financier le plus élevé est celui dont le poids maximal est le plus faible. Bien sûr, puisque vous souhaitez probablement utiliser de beaux entiers, vous pouvez simplement modifier les comparaisons au lieu d’utiliser les inverses.

Answer 5

Vous souhaitez optimiser un [ http://en.wikipedia.org/wiki/Flow_network ] . La capacité est la limite de poids maximale de la route; et le débit est le poids du camion.

Answer 6

Vous pouvez adopter une sorte d’approche d’extension minimale. Connectez les nœuds un bord à la fois, en commençant par les débits les plus forts, jusqu'à ce que A et B soient connectés. Le dernier bord ajouté au graphique est le bord de flux le plus bas que vous devrez traverser pour aller de A à B. Ce n'est probablement pas la solution la plus efficace (O (N ² ) dans le cas le plus défavorable) , mais au moins c'est simple.

Answer 7

Il ne s'agit ni d'un problème de chemin le plus court, ni d'un problème de débit maximal. Il n'y a pas de problème. Il a déclaré - voulez un poids maximal pour tous les chemins A à B. Donc, générez tous les chemins A à partir de BFS. Pour tous les chemins se terminant par B, obtenez le poids minimal des arêtes du chemin.

Answer 8

Utilisez l'algorithme de Dijkstra avec l'inverse du poids maximal du camion comme coût marginal, et le maximum de poids de bord individuels comme coût total de la route.

i.e. edge_cost est égal à 1 / (poids maximal du camion autorisé) le total_cost d'une route donnée est le maximum des <=> individuelles de toutes les arêtes de la route.

Answer 9

Diverses réponses ci-dessus proposent simplement un algorithme de Dijkstra avec une fonction de pondération modifiée. Par exemple, w(e) = -c(e) ou 'w (e) = 1 / c (e)', où w(e) est le poids d’une arête utilisée par l’algorithme et c(e) est la capacité de cette arête dans la formulation du problème original.

Cela ne fonctionne pas.

On peut facilement créer des contre-exemples qui donneraient des résultats incorrects. Par exemple, considérons le graphique:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Supposons que la valeur de a ('distance du noeud d dans la formulation de l'algorithme) soit égale à zéro. Les deux chemins de (-3)+(-3)+(-3) = -9 à -3 sont équivalents à ce problème. Cependant, si nous annulons simplement la capacité de bord, la distance (d), en utilisant le long chemin, est (1/3)+(1/3)+(1/3)=1 en utilisant le court chemin, elle sera (1/3). Si nous inversons la capacité du bord, la distance (d) en utilisant le long chemin serait +, alors que ce serait simplement < en utilisant le court.

Ce que travaillera , c'est de modifier l'étape de relaxation de l'algorithme, c'est-à-dire au lieu d'utiliser les fonctions d'addition (min) et de moins que (>), en utilisant respectivement les fonctions <= > et supérieur à (@), et utilisez un tas max au lieu d’un tas min. Nous pourrions éviter les deux dernières modifications si nous annulions les poids des arêtes et si nous utilisions moins que, mais nous ne pouvons éviter de remplacer a @ a = a, car nous avons besoin d'un opérateur a=0 où u pour toutes les d(u) valeurs, <=> ne fonctionne que pour <=>.

La seule réponse correcte que je vois est donc la toute première réponse donnée par Keith Randall.

Un bon exercice serait de prouver formellement que l’algorithme modifié est correct. Ce qu'il faut prouver, c'est: - Si <=> est le noeud avec la valeur maximale <=> à toute itération de boucle, aucun chemin impliquant des noeuds non marqués ne peut créer un chemin pour <=> donner une distance supérieure à <=>.

Intuitivement, il est facile de voir, puisque tous les autres nœuds non marqués ont une distance inférieure (ou égale à) la distance de 'u' (car nous choisissons <=> comme celui avec la distance maximale), et la distance du Les chemins générés sont générés par des invocations successives de <=>, ils ne peuvent donc que devenir plus petits, pas plus grands.