Trouver le chemin avec le maximum de capacité minimale dans le graphe

Je suis d'aider un ami avec un travail lié projet où il faut calculer la capacité maximale d'un nœud a vers le nœud b, où le bord a une capacité. Toutefois, le maximum de capacité dans un chemin de a à b est limitée par le bord avec la plus faible capacité.

Laissez-moi vous expliquer avec un exemple simple
Trouver le chemin avec le maximum de capacité minimale dans le graphe

De sorte que le graphe est un graphe orienté de la pondération des arêtes, et il peut être cyclique. Le chemin d'accès avec la capacité la plus élevée serait s->b->t et ont la capacité de 250, depuis que le bord est du réglage de la limite.

J'ai fait un peu de lecture et découvert que ce type de problème est un "Le plus large du problème de chemin d'accès" ou je dirais que c'est quelque chose comme un chemin avec un maximum de capacité minimum, mais je n'ai pas trouvé d'exemples ou de toute pseudo-code expliquant comment y remédier.

Je pensais à quelque chose dans les lignes de trouver tous les chemins de s à t, à l'aide de la BFS et en quelque sorte uniquement pour permettre la visite d'un nœud une fois dans un chemin, et ensuite trouver la valeur minimale dans le chemin, cela fonctionnerait-il?

InformationsquelleAutor Cheesebaron | 2013-08-31
  1. 13

    Je voudrais utiliser une variante de Dijkstra est. J'ai pris le pseudo-code ci-dessous directement à partir de Wikipedia et a changé 5 petites choses:

    1. Renommé dist à width (ligne 3)
    2. Initialisé chaque width à -infinity (ligne 3)
    3. Initialisé la largeur de la source à infinity (ligne 8)
    4. Définir la finition critère de -infinity (ligne 14)
    5. Modifié la fonction de mise à jour et de signer (ligne 20 + 21)
    1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 //Initializations
3          width[v] := -infinity  ;                                //Unknown width function from 
4                                                                  //source to v
5          previous[v] := undefined ;                              //Previous node in optimal path
6      end for                                                     //from source
7      
8      width[source] := infinity ;                                 //Width from source to source
9      Q := the set of all nodes in Graph ;                        //All nodes in the graph are
10                                                                 //unoptimized – thus are in Q
11      while Q is not empty:                                      //The main loop
12          u := vertex in Q with largest width in width[] ;       //Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            //all remaining vertices are
16          end if                                                 //inaccessible from source
17          
18          for each neighbor v of u:                              //where v has not yet been 
19                                                                 //removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 //Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           //Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

    Certains (handwaving) explication des raisons pour lesquelles cela fonctionne: vous commencez avec la source. À partir de là, vous avez la capacité infinie à lui-même. Maintenant à vous de vérifier tous les voisins de la source. Supposons que les bords n'ont pas tous la même capacité (dans votre exemple, dire (s, a) = 300). Ensuite, il n'y a pas de meilleure façon d'atteindre b puis via (s, b), de sorte que vous savez le meilleur des cas, la capacité de b. Vous continuer à aller dans le meilleur des voisins de cet ensemble de sommets, jusqu'à ce que vous atteindre tous les sommets.

    • Puis-je remplacer les sommets avec les bords? Rappelez-vous mon graphe a pondéré les bords et pas des sommets. Aussi comment puis-je spécifier la destination de vertice?
    • c'est exactement ce qui se passe. L'interprétation de width[v] est 'la largeur de la plus vaste chemin de s à v'. Le bord des poids sont donnés par width_between(u, v) (certes, ça pourrait être pas intuitif, mais j'ai juste copié le code wiki). Vous pouvez stopper simplement les tests if u = destination en ligne 14.
    • Merci un tas. Votre pseudo code a beaucoup aidé!
    InformationsquelleAutor Vincent van der Weele
  2. 9

    La réponse ci-dessus a été très bien expliqué. Juste au cas où quelqu'un a besoin d'une explication de l'exactitude de l'algorithme, ici vous allez:

    Preuve:

    À n'importe quel point dans l'algorithme, il y aura 2 ensembles de sommets A et B. Les sommets seront les sommets auxquels le bon minimum au maximum de la capacité de chemin a été trouvé. Et l'ensemble B a sommets auxquels nous n'avons pas trouvé la réponse.

    Inductive Hypothèse: À chaque étape, tous les sommets de définir Une ont les bonnes valeurs minimum au maximum de la capacité de leur chemin d'accès. c'est à dire., toutes les versions précédentes sont correctes.

    De l'exactitude de la base de cas: Quand la série a, le sommet S seulement. Ensuite, la valeur de S est l'infini, ce qui est correct.

    Dans l'itération en cours, nous avons mis en

    val[W] = max(val[W], min(val[V], width_between(V-W)))

    Inductive étape: Supposons que W est le sommet de la série B avec le plus grand val[W]. Et W est retiré de la file d'attente et W a été de définir la réponse de val[W].

    Maintenant, nous avons besoin de montrer que tous les autres S-W voie a une largeur <= val[W]. Ce sera toujours vrai, car toutes les autres façons d'atteindre W de passer par un autre vertex (appelons-la X) dans l'ensemble B.

    Et pour tous les autres sommets de X dans l'ensemble B, val[X] <= val[W]

    Ainsi, tout autre chemin d'accès à W sera contraint par val[X], ce qui n'est jamais supérieure à val[W].

    Ainsi, l'estimation actuelle de val[W] est optimale, et donc l'algorithme calcule les valeurs correctes pour tous les sommets.

    InformationsquelleAutor Nikunj Banka