Задача използваща алгоритъм на Дейкстра

Нека s е връх в граф с неотрицателни дължини на дъгите и се интересуваме от дължините на най-късите пътища от s до всички останали върхове. Едно решение ни предлага търсенето в ширина: всяко ребро с дължина L разделяме на L ребра с дължина 1 и прилагаме bfs. Тази идея работи само теоретично – дължините на ребрата могат да бъдат хиляди или милиони и алгоритъмът ще работи преобладаващо с изкуствени върхове. Ще усъвършенстваме bfs, като вместо обикновена опашка ще използваме приоритетна опашка. За реализацията на приоритетна опашка може да се използва пирамида. Пирамидата е структура от данни, която съхранява множество от елементи, имащи ключове за сравнение. Операциите с пирамидата h, които ще използваме са:

deletemin(h,x) – изключване от пирамидата h на елемента с минимален ключ и записването му в x.

Алгоритъм на Дейкстра

heap h;

for (u=1; u<=n; u++)

  { dist[u]=infinity;

    prev[u]=0;

  }    

dist[s]:=0;

insert(h,s,0);

while (h is not empty)

         for(v in Adj(u)))

      if (dist[v] > dist[u]+length[u][v])

        { dist[v] = dist[u]+length[u][v];

          prev[v] = u;

          insert(h,v,dist[v]);

        }

  }