Trouver le chemin avec le poids minimal maximal

Question

Je suis en train de travailler sur un algorithme pour trouver un chemin à travers un graphe orienté. Ce n'est pas un chemin conventionnel et je ne peux pas trouver aucune référence à quelque chose comme cela se fait déjà.

Je veux trouver le chemin qui a le poids minimum maximum.

i.e.. S'il y a deux chemins ayant des poids 10> 1> 10 et le 2-> 2> 2, alors le second chemin est considéré comme meilleur que le premier parce que le poids minimum (2) est supérieure au poids minimal de la première (1 ).

Si quelqu'un peut trouver une façon de le faire, ou tout simplement me diriger dans la direction d'une matière de référence, il serait extrêmement utile:)

EDIT :: Il semble que j'oublié de mentionner que je suis en train d'obtenir d'un sommet spécifique à un autre sommet spécifique. Tout à fait important là: /

EDIT2 :: Comme quelqu'un l'a ci-dessous, je dois souligner que les poids de bord sont non négatifs.

Answer 1

Utilisez soit Prim ou algorithme Kruskal. Il suffit de les modifier afin qu'ils arrêtent quand ils découvrent que les sommets que vous posez au sujet sont connectés.

EDIT: Vous demandez au minimum au maximum, mais votre exemple ressemble à ce que vous voulez au maximum au minimum. En cas de minimum maximum l'algorithme de Kruskal ne fonctionnera pas.

EDIT: L'exemple est d'accord, mon erreur. Seul l'algorithme de Prim fonctionnera alors.

Answer 2

Je copie cette réponse et en ajoutant en ajoutant ma preuve de correction pour l'algorithme:

Je voudrais utiliser une variante de de Dijkstra. Je pris le pseudo-code ci-dessous directement de Wikipedia et seulement changé 5 petites choses:

1. Redénommé dist à width (à partir de la ligne 3)
2. initialisée chaque -infinity à infinity (ligne 3)
3. initialisée la largeur de la source à (s, a) = 300 (ligne 8)
4. Définir le critère d'arrivée pour b (ligne 14)
5. Modification de la fonction de mise à jour et signe (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

Quelques explications (de argument qualitatif) pourquoi cela fonctionne: vous commencez avec la source. De là, vous avez une capacité infinie à lui-même. Maintenant, vous vérifiez tous les voisins de la source. On suppose que les bords n'ont pas tous la même capacité (dans votre exemple, disent (s, b)). Ensuite, il n'y a pas de meilleur moyen d'atteindre puis par <=> <=>, donc vous savez la meilleure capacité de cas de <=>. Vous continuez d'aller aux meilleurs voisins de l'ensemble connu des sommets, jusqu'à atteindre tous les sommets.

Preuve de correction de l'algorithme:

A tout moment de l'algorithme, il y aura 2 ensembles de sommets A et B . Les sommets A seront les sommets auxquels le chemin de la capacité minimale maximale correcte a été trouvé. Et l'ensemble B a des sommets que nous avons pas trouvé la réponse.

hypothèse de récurrence : A chaque étape, tous les sommets dans l'ensemble A ont les valeurs correctes de la trajectoire de capacité minimum maximum à eux. à-dire., toutes les itérations précédentes sont correctes.

Correction de cas de base : lorsque l'ensemble A est le sommet S uniquement. Ensuite, la valeur de S est infini, ce qui est correct.

Dans l'itération actuelle, nous avons mis

  

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

étape inductive : Supposons, W est le sommet dans la série B avec le plus grand val [W]. Et W est dequeued de la file et W a été réglée la réponse val [W].

Maintenant, nous devons montrer que tout autre voie S-W a une largeur <= val [W]. Ce sera toujours vrai, car toutes les autres façons d'atteindre W passera par un autre sommet (appeler X) dans l'ensemble B.

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

Ainsi, toute autre voie à W sera limitée par val [X], qui est supérieure à jamais val [W].

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

Answer 3

Vous pouvez également utiliser le paradigme « recherche binaire sur la réponse ». Cela est, faire une recherche binaire sur les poids, les tests pour chaque poids que vous pouvez w trouver un chemin dans le graphe en utilisant uniquement des bords de poids supérieur à O(|E|*log(max W)).

Le plus grand pour lequel vous O(|E|log |V|) pouvez (trouvé par la recherche binaire) donne la réponse. Notez que vous ne devez vérifier si un chemin existe, si juste O (| E |) en largeur / recherche en profondeur d'abord, pas un plus court chemin. Il est donc dans l'ensemble <=>, comparable à la Dijkstra / Kruskal / Prim de <=> (et je ne peux pas voir immédiatement une preuve de ceux-ci, aussi).

Answer 4

Ceci peut être résolu en utilisant un algorithme de style BFS, mais vous avez besoin de deux variantes:

• Au lieu de marquer chaque nœud comme « visité », vous marquez avec le poids minimum le long du chemin que vous avez pris pour y arriver.

Par exemple, si I et J sont voisins, a une valeur I w1, et le poids de l'arête entre eux est w2, alors J = min (w1, w2).

• Si vous atteignez un nœud marqué avec la valeur w1, vous pourriez avoir besoin de faire remarquer et de traiter à nouveau, si l'attribution d'une nouvelle valeur w2 (et w2> w1). Cela est nécessaire pour vous assurer d'obtenir le maximum de tous les minimums.

Par exemple, si I et J sont des voisins, j'a valeur w1, J a une valeur w2, et le poids du bord entre eux est w3, alors si min (w2, w3)> w1 vous devez remarquer J et processus tout cela à nouveau ses voisins.

Answer 5

Je ne suis pas sûr que Prim fonctionnera ici. Prenez cette contre-:

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

Si vous appliquez Prim pour trouver le chemin de maxmin de 1 à 3, à partir de 1 sélectionnera le chemin 1 --> 2 --> 3, alors que la distance de maxmin est atteint pour le chemin qui passe par 4.

Answer 6

Ok, répondre à ma propre question ici juste pour essayer d'obtenir un peu de commentaires que j'avais sur la solution provisoire, j'ai travaillé avant de poster ici:

Chaque nœud stocke un « fragment de chemin », c'est le chemin complet lui-même jusqu'à présent.

0) définir le sommet en cours au sommet à partir
1) Générer tous les fragments de chemin de ce sommet et de les ajouter à une file d'attente prioritaire
2) Prenez le fragment du haut de la file d'attente prioritaire, et définissez le sommet en cours au sommet fin de ce chemin
3) Si le sommet actuel est le sommet cible, puis retourne le chemin
4) goto 1

Je ne suis pas sûr que cela va trouver le meilleur chemin bien, je pense que la condition de sortie à l'étape trois est un peu ambitieux. Je ne peux pas penser à une meilleure condition de sortie cependant, puisque cet algorithme ne pas les sommets proches (un sommet peut être référencé en autant de fragments de chemin comme il aime) vous ne pouvez pas attendre jusqu'à ce que tous les sommets sont fermés (comme Dijkstra pour exemple)

Answer 7

Vous pouvez toujours utiliser! De Dijkstra

Au lieu d'utiliser +, utilisez l'opérateur min ().
De plus, vous aurez envie d'orienter le tas / priority pour que les choses les plus importantes sont sur le dessus.

Quelque chose comme cela devrait fonctionner: (je l'ai sans doute manqué quelques détails de mise en œuvre)

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

Il est garanti que chaque fois que vous arrivez à un nœud que vous avez suivi un chemin optimal (puisque vous trouverez toutes les possibilités dans l'ordre décroissant, et vous ne pouvez jamais améliorer votre chemin en ajoutant un bord)

Les limites de temps sont les mêmes que de Dijkstra -. O (Vlog (E))

EDIT: oh, attendez, c'est essentiellement ce que vous avez publié. LOL.