Dijkstra algorithme propriété

Question

Dijkstra(G,w,s) { 
    ISS(G,s); 
    let S be an empty set 
    let Q be a priority queue, initialized with V[G] 
    while Q is not Empty: 
     u<-extractMin(Q); 
     add u to S 
     for each vertex v neighbor of u 
      Relax(u,v,w); 
} 

ma question est, pourquoi est-il important de choisir le MINIMUM d [v] de tout v dans Q à chaque étape de l'algorithme dans la boucle while, ce qui est Gonna heppen si nous ne choisir le minimum ? Je veux dire par la façon dont je le vois, toutes les arêtes (u, v) vont se relaxer dans un ordre de grandeur (signifie que si - s-> u-> v et (s, v) pas dans E alors (s, u) se relâcherait avant (u, v)), alors pourquoi est-il important de choisir le d [v] minimal à chaque fois?

suppose qu'il existe une fonction extractMaxFiniteD (Q) qui renvoie sommet v tel qu'il a max d [v] soit fini dans Q

laisse supposer que l'on change de ligne u < -extractMaxFiniteD (Q); quelqu'un peut-il me dessiner un graphique dans lequel l'alg modifié échouerait - ou même mieux - quelle propriété du chemin le plus court serait violée?

Je sais que cette question pourrait être assez difficile et abstraite, mais ce serait génial si some1 pourrait m'aider avec cela.

Answer 1

exemple:

nœuds: a, b, c
bords (et poids): (a, b, 1) (a, c, 10) (b, c, 1)

essayez votre algorithme à ce sujet. vous constaterez que le chemin le moins coûteux vers c est 10 quand c'est évidemment 2.

lorsque vous supprimez un nœud de Q vous ne relâchez plus jamais, si vous supprimez un nœud au coût maximal alors vous ne faites pas t envisager des moyens moins expesifs pour atteindre ce noeud. Si vous ne voulez pas sélectionner le nœud minimal de Q alors vous ne pouvez pas le retirer de Q non plus, vous devez le garder dans l'ensemble afin qu'il puisse être assoupli lors des prochaines itérations. c'est essentiellement ce que fait l'algorithme bellman-ford.

Answer 2

L'idée principale de l'algorithme de Dijkstra est la suivante: lorsque vous prenez un sommet sur Q, ce sommet est bon. Vous n'aurez pas à vous détendre dans le futur.

Si vous prenez un élément aléatoire de Q, cette condition ne tient pas - une fois que vous avez pris un sommet v sur Q, il n'est pas garanti la d[v] est en effet le plus court chemin vers v.

Si vous prenez le minimum - il est garanti, car si v est minime dans Q, puis pour chaque u dans Q, d[u] >= d[v], donc peu importe que vous relexations faire ensuite - vous ne pouvez pas améliorer d[v]