Poniższy algorytm służy do wyznaczania w grafie ciągu wierzchołków u_s, u_s+1...u_t tworzących drogę między wierzchołkami u_s i u_t o długości d(u_s,u_t). jest on najczęściej używany razem z algorytmem wyznaczania najmniejszej odległości między wierzchołkami (algorytm Forda-Bellmana, algorytm Dijkstry). Po wyznaczeniu najkrótszej odległości d(u_s,u_t) między parą wierzchołków w grafie możemy skonstruować drogę między tymi wierzchołkami taką, że suma wag jej krawędzi jest równa d(u_s,u_t).
Chcemy wyznaczyć drogę między wierzchołkami u_s i u_t o najkrótszej długości.
Załóżmy więc, że dla danego grafu opisanego za pomocą macierzy wag krawędzi A wywołaliśmy algorytm wyznaczania najkrótszej odległości od ustalonego wierzchołka (u_s) do wszystkich pozostałych i w jego wyniku otrzymaliśmy wektor D- tablicę tych odległości. Z wektora tego odczytujemy najmniejszą odległość między wierzchołkami u_s i u_t: D[u_t]=d(u_s, u_t).
Po wykonaiu poniższego algorytmu na stosie otrzymamy ciąg wierzchołków u_s...u_t będących drogą między wierzchołkiem u_s i u_t o długości d(u_s, u_t).
Algorytm przebiega w sposób następujący:

1. Zainicjuj stos S, odłóż na stos wierzchołek końcowy, czyli u_t, podstaw v=u_t
2. while v<>u_s do
3. {
4. znajdź wierzchołek u taki, że D(v)=D(u)+A[u,v]
5. odłóż u na stosie S
6. podstaw v=u
7. }

Przeanalizujmy teraz prosty przykład:
oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy U_s=1, symbol "*" oznacza nieskończoność:

Jak widać z macierzy wag graf ten ma krawędzie o ujemnych wagach, musimy więc zastosować algorytm Forda-Bellmana. W wyniku jego działania otrzymamy wektor D postaci: D[1]=0, D[2]=2, D[3]=4, D[4]=2, D[5]=5, D[6]=4. W implementacji umieszczonej na stronie wierzchołkiem, względem którego wyznacza się najkrótsze odległości jest wierzchołek o indeksie 1, dlatego też D[1]=0. Musimy teraz wybrać drugi wierzchołek- końcowy, niech będzie to wierzchołek nr. 5. Z wektora D odczytujemy najmniejszą odległość między wierzchołkami 1 i 5 D[5]=d(1,5)=5. chcemy wyznaczyć drogę łączącą wierzchołek 1 i 5 o długości równej 5.
Po wykonaniu pierwszej linii algorytmu otrzymamy anstępujące parametry:

Stos={5}

v=5

D[v]=5

u=?

D[u]+A[u,v]=?

Poszukujemy teraz wierzchołka u. Logika nakazuje sprawdzanie wartości D[u]+A[u,v] tylko dla tych wierzchołków u, które są poprzednikami wierzchołka v. W naszym przypadku poprzednikami wierzchołka 5 są wierzchołki 2, 3 i 6. Sprawdzamy więc: D[2]+A[2,5]=2+4=6<>D[5], D[3]+A[3,5]=4+3=7<>D[5] a D[6]+A[6,5]=4+1=5=D[5]. Znależliśmy wierzchołek u=6 wykonujemy zatem instrukcje 5 i 6 algorytmu:

Stos={5,6}

v=6

D[v]=4

u=?

D[u]+A[u,v]=?

Tym razem nie mamy zbyt dużego wyboru, gdyż jedynym poprzednikiem wierzchołka nr. 6 jest 4. A więc D[4]+A[4,6]=2+2=4=D[6], zatem m=4. Dalej algorytm przebiega podobnie:

Stos={5,6,4}	v=4	D[v]=2	u=3	D[u]+A[u,v]=4+(-2)=4
Stos={5,6,4,3}	v=3	D[v]=4	u=1	D[u]+A[u,v]=0+4=4

Tu algorytm się kończy, gdyż w następnej iteracji v=1. A zatem droga między wierzchołkiem 1 i 5 o długości 5 jest następująca: (1,3,4,6,5)