J'ai ce problème: " chemin le plus court avec un bord scippable . Compte tenu d'un digraphe pondéré de bord, concevoir un Je ne comprends pas ce qu'ils veulent que je fasse. Qu'est-ce que cela signifie de changer le poids à zéro? Je pense que je peux changer n'importe quel bord dans n'importe quel chemin le plus court à zéro et ce sera toujours le plus court. E * log (v) algorithme pour trouver un algorithme le plus court chemin de S à t où vous pouvez modifier le poids d'un bord d'un bord à zéro. Supposons que les poids des bords sont non négatifs. "
5 Réponses :
Utilisez d'abord DIJKSTRA pour trouver la longueur S (V) du chemin le plus court de S à v pour chaque sommet v < / code>. Ensuite, utilisez dijkstra pour trouver la longueur t (v) du chemin le plus court de V à t pour chaque sommet v v . Ensuite, pour chaque bord (v, w) trouver la somme s (v) + t (w) en utilisant les règles ci-dessus. Enfin, choisissez le chemin minimum.
(v, w) poids et trouvez le chemin le plus court que traversez (v, w)
L'algorithme fonctionnera-t-il toujours? Considérez le bord (U, V) étant réglé sur 0. Désormais si le chemin le plus court de T à V passe à travers ce bord? Par exemple dans ce graphique. imgur.com/qtawr25 sera votre algorithme? Source = 1, cible = 4, bordedu-v = bord de 2 à 3.
Je suis sûr que cela fonctionne, mais je ne reçois pas votre exemple car il n'y a pas de chemin de la source à la cible.
@Bartoszmarcinkowski Juste pour ajouter à votre réponse, nous pouvons généraliser en demandant à l'op d'utiliser l'algorithme de chemin le plus court au lieu de l'algorithme de Dijkstra spécifique spécifiquement.
@Bartoszmarcinkowski "Ensuite, utilisez Dijkstra pour trouver la longueur T (V) du chemin le plus court de V à T de V à t pour chaque sommet v." - Cela ne fait pas l'algorithme O (v * e * logv) car l'algorithme doit exécuter DIJKSTRA sur chacun sommet?
@ user1559897 Non, vous n'exécutez pas Dijkstra pour chaque sommet, seulement pour deux d'entre eux: s et t.
Le problème est simple.
Supposons que vous ayez un chemin le plus court avec un bord skippable, P = V1, ..., VI, VI + 1, ..., VM
et (VI, VI + 1) est un bord sauté
Évidemment, un chemin (V1, ..., VI) est un chemin le plus court entre V1 et VI
et un chemin (VI + 1, ..., VM) est un chemin le plus court entre VI + 1 et VM
Définir D (x, y) comme la longueur du chemin le plus court entre le noeud x et le nœud Y
Vous pouvez simplement trouver d (s, x) et d (x, t) pour tous les nœuds x par dijkstra algorithme
Et maintenant, nous devons choisir le bord sauté un par un.
En d'autres termes, la longueur du chemin le plus court avec un bord skippable est
min (d (s, u) + d (v, t)) pour tout bord (U, V) dans le graphique
et la complexité temporelle est O (E Log V) à cause de l'algorithme de Dijkstra
Bien que l'autre réponse soit d'abord et dit la même chose, celle-ci est bien mieux expliquée. +1!
Les réponses précédentes semblent supposer que Dijkstra donne la distance la plus courte de chaque sommet à chaque sommet, mais ce n'est pas le cas.
Si vous exécutez Dijkstra une seule fois, à partir de s, vous avez le chemin le plus court de S à chaque sommet.
Pour trouver la distance la plus courte de chaque sommet à t, il est nécessaire d'exécuter Dijkstra à nouveau à partir de t après l'inversion de chaque bord du graphique.
La solution complète est la suivante:
1) Exécutez Dijkstra sur le graphique G à partir de S pour obtenir la distance la plus courte T (V) entre s et n'importe quel v.
2) Inverser tous les bords pour obtenir le graphique inversé G '
3) Exécutez Dijkstra sur le graphique G 'à partir de T pour obtenir la distance la plus courte R (V) entre T et tout V.
4) Celui à sauter est le bord E (V1 -> V2) pour lequel T (v1) + R (v2) est minimum.
5) Le chemin à suivre est une concaténation du chemin le plus court entre S et V1 donné par la première dijkstra et le chemin le plus court entre V2 et T donné par la deuxième dijkstra.
Merci @marco Altieri RAW.GITUBUSERCONTENT. Com / Himanshu-Tamrakar / Algorithmes / Maste R / ...
Les réponses existantes sont bonnes et correctes, mais une autre idée plus intuitive pour moi est de transformer le graphique et d'utiliser une approche en couches:
g et appelez-le g '
- pour chaque bord
(u, v) dans g , crée un bord (u, v ') dirigé à partir de u (dans g ) à v ' (dans g' ), de poids 0 . < / li>
- Utilisez n'importe quel algorithme de chemin le plus court standard tel que Dijkstra pour calculer le chemin le plus court de
S à t '. .
Définitivement la meilleure réponse!
Comment affirmer l'exactitude de cet algorithme?
Je suis tombé sur cette question lorsque je faisais le cours de Princeton Algorithmes sur Coursera. Je reçois la réponse acceptée, mais je suis arrivé à une approche que je pense devoir fournir le chemin le plus court avec un bord sauté de S à tout autre bord.
Nous allons utiliser la classe suivante pour stocker des informations de bord pondérées, dirigées: p> Cependant, nous ajouterons également une classe de décorateur: p> la plus longue ici représentant le plus long segment connu de la Le chemin le plus court connu du sommet. p> Le reste est assez standard Djikstra d'une file d'attente de priorité minimale indexée et tout, mais avec une méthode de relaxation légèrement modifiée: P> private void relax(EdgeWeightedDigraph G, int e) {
SkipPathEdge parentEdge = edgeTo[e];
for (DirectedEdge edge : G.adj(e)) {
double longest = Math.max(parentEdge.longest, edge.getWeight());
double adjustment = longest - parentEdge.longest;
SkipPathEdge childEdge = new SkipPathEdge(edge, longest);
int from = edge.getFrom(), to = edge.getTo();
if (distTo[to] > distTo[from] + edge.getWeight() - adjustment) {
distTo[to] = distTo[from] + edge.getWeight() - adjustment;
edgeTo[to] = childEdge;
if (minPQ.contains(to)) {
minPQ.changeKey(to, distTo[to]);
} else {
minPQ.addKey(to, distTo[to]);
}
}
}
}
"Je pense que je peux changer n'importe quel bord dans n'importe quel chemin le plus court de zéro et ce sera toujours le plus court." - Imaginez un seul bord qui attache le début à la finition, avec poids 9999999.
Que veux-tu dire? Si j'ai un chemin le plus court et changez cet énorme bord à zéro, ce bord deviendra le nouveau chemin le plus court?
Oui, c'est exactement ce que je veux dire. Donc, le problème n'est pas aussi simple que "trouver le chemin le plus court et supprimer le bord le plus long qui en fait partie". Cela n'est pas aussi simple que de supprimer le bord le plus long sur le graphique. Je devrais prendre un peu de temps pour réfléchir à la façon de résoudre ce problème.