Tout algorithme qui considère réellement tous les chemins de u à v prendra un temps exponentiel, car il existe un nombre exponentiel de tels chemins - considérons une échelle, ou une grille de nœuds 2xN - pour aller d'une extrémité à l'autre la dimension longue vous donne au moins N choix indépendants, donc au moins 2^N chemins possibles.
Je pense que vous pouvez modifier l'algorithme de Dijkstra pour ce faire. Il y a un pseudo code au https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode. En tant que première modification, changez la ligne 6 pour mettre toutes les distances initiales à zéro. Nous devons penser aux invariants, et notre premier invariant peut être que dist [v] est la valeur maximum pour le bord minimum dans un chemin vers v, pour tous les chemins vus jusqu'ici. Comme précédemment, nous avons mis prev [v] à undefined et ajouté v à Q, la file d'attente contenant tous les nœuds actuellement à l'étude. Comme dernière partie de l'initialisation, nous définissons dist [source] = infinity - not 0. Vous pouvez considérer cela comme un hack, ou comme un moyen de définir la longueur minimale de l'arête dans un chemin de longueur 0 de v à v qui ne pas de bords.
Maintenant nous avons que Q contient tous les nœuds où la valeur maximale pour le bord minimum est encore à l'étude, et que cette valeur pour tous ces nœuds ne fera qu'augmenter. Maintenant nous retirons de Q le noeud u avec la valeur maximum de dist [u] - c'est l'étape 13 modifiée avec min changé en max. Pour chaque voisin v de u nous calculons min (dist [v], length (u, v)). Il s'agit d'un nouveau candidat pour la longueur d'arête minimale possible le long de n'importe quel chemin de la source vers u, donc si elle est plus grande que dist [u], nous mettons dist [u] à cette valeur. Notez que cela signifie qu'aucun élément u de Q n'aura jamais dist [u] fixé à une valeur supérieure à la valeur de dist [v] pour l'élément v de Q que nous venons de supprimer, qui était un maximum de cette valeur dans la file d'attente à ce moment-là. Cela signifie qu'une fois que nous avons supprimé un élément v de la file, sa valeur dist [v] a été calculée pour de bon et ne peut être augmentée par aucun calcul ultérieur. Attention, nous avons juste changé dist [u] pour un noeud de notre file d'attente Q. Si Q est implémenté avec une structure de données telle qu'une file d'attente prioritaire, cela signifie probablement que l'implémentation devra vous retirer de la file d'attente prioritaire valeur de dist [u], puis réinsérez-le sous la nouvelle valeur de dist [u]. La correction découle des invariants - à chaque fois que nous avons dist [v] la valeur maximale du bord minimum le long de chaque chemin considéré jusqu'ici, et quand nous retirons v de la file, nous savons - parce qu'il a une valeur maximale pour tout reste dans la file d'attente - qu'aucun des autres chemins que nous pourrions considérer ne peut changer cette valeur.
Le temps pris pour faire ceci est le même que Dijkstra, et pour la même raison. Nous entrons chaque élément dans la file d'attente une fois, au début, et nous retirons tous les éléments de la file une fois. Cela nous indique combien de fois nous exécutons l'opération de suppression à la ligne 14.
(maximum des bords pondérés minimum semble une chose étrange à calculer - est-il une application intéressante ici, ou est-ce un exercice artificiel pour vous faire penser à l'algorithme de Dijkstra)
Je vous recommande de consulter un manuel d'algorithme (ou Wikipedia). – charlesreid1