Пошук найкоротшої відстані між вершинами графа (алгоритм Дейкстри).

Алгоритмзнаходить найкоротші шляхи від деякої вершини до всіх інших вершин графа за умови невід’ємності ваг його ребер.

Крок 1. Вершині , від якої шукаються найкоротші шляхи, приписати постійну позначку . Всім іншим вершинам приписати тимчасові позначки .

Крок 2. Для всіх ребер , інцидентних вершині , та таких, що мають тимчасову позначку, змінити позначки у відповідності з формулою , де — вага ребра .

Крок 3. Знайти вершину з мінімальною тимчасовою позначкою. Позначити таку позначку як постійну. Позначити ребро, що з’єднує цю вершину з її прообразом, стрілкою. Прийняти цю вершину у якості та перейти до кроку 2.

Алгоритм повторюють доти, доки всі вершини графа не отримають постійні позначки. По закінченні роботи алгоритму позначка деякої вершини дає довжину найкоротшого шляху, від цієї вершини до початкової, а сам шлях можна відновити за допомогою ребер зі стрілками.