Свойство алгоритма Дейкстры

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);
}

мой вопрос: почему важно выбрать МИНИМАЛЬНОЕ d [v] всех v в Q на каждом шаге алгоритма в цикле while, что будет, если мы не выберем минимум?

Я имею в виду, как я вижу, все ребра (u, v) будут ослаблены в первом порядке (это означает, что если - s-> u-> v и (s, v) нетв E тогда (s, u) расслабится раньше (u, v)), так почему важно каждый раз выбирать минимальное d [v]?

предположим, что существует функция extractMaxFiniteD (Q), которая возвращает вершину v так, что она имеет максимальное значение d [v], конечное в Q

, давайте предположим, что мы изменили эту строку на u <-extractMaxFiniteD(Q);Может ли кто-нибудь нарисовать мне график, на котором измененный alg потерпит неудачу - или даже лучше - какое свойство кратчайшего пути получит фиолетовый цвет?если бы кто-нибудь мог мне помочь с этим. </p>

Answer 1

Основная идея алгоритма Дейкстры заключается в следующем: когда вы берете вершину из Q, эта вершина хороша. Вам не придется расслабляться в будущем.

Если вы берете случайный элемент из Q, это условие не выполняется - после того, как вы взяли вершину v из Q, не гарантируется, что d[v] действительно самый короткий путь к v.

Если вы берете минимальное - это гарантировано, поскольку, если v минимально в Q, то для каждого u в Q, d[u] >= d[v], таким образом, независимо от того, какие реакции вы делаете дальше, не может улучшиться d[v]

Answer 2

пример:

узлы: a, b, c
ребра (и веса): (a, b, 1) (a, c, 10) (b, c, 1)

попробуй свой алгоритм на этом. вы обнаружите, что путь с наименьшей стоимостью к c равен 10, когда его очевидно 2.

Когда вы удаляете узел из Q, вы больше не расслабляете его, если вы удаляете узел с максимальной стоимостью, тогда вы не рассматриваете менее сложные способы достижения этого узла.

если вы не хотите выбирать минимальный узел из Q, тогда вы не можете удалить его из Q, вы должны оставить его в наборе, чтобы его можно было ослабить в будущих итерациях это в основном то, что делает алгоритм bellman-ford .