Thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại được Dijkstra đề nghị áp dụng cho trường hợp đồ thị có hướng với trọng số không âm. Thuật toán được thực hiện trên cơ sở gán tạm thời cho các đỉnh. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất tới đỉnh đó.Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp, mà ở mỗi bước lặp một số đỉnh sẽ có nhãn không thay đổi, nhãn đó chính là độ dài đường đi ngắn nhất từ s đến đỉnh đó.

Giả mã

void Dijkstra(void)

/*Đầu vào G=(V, E) với n đỉnh có ma trận trọng số A[u,v]≥ 0; s ϵ V */

/*Đầu ra là khoảng cách nhỏ nhất từ s đến các đỉnh còn lại d[v]: v ϵ V*/

/*Truoc[v]: ghi lại đỉnh trước v trong đường đi ngắn nhất từ s đến v*/

{

/*Bước 1: Khởi tạo nhãn tạm thời cho các đỉnh*/

for ( vϵV ) {

d[v] = A[s,v];

truoc[v]=s;

}

d[s]=0;

T = V\{s}; /*T là tập đỉnh có nhãn tạm thời*/

/* Bước lặp */ while (T != Ø ) {

Tìm đỉnh u ϵ T sao cho d[u] = min

{ d[z] | z ϵ T}; T= T\{u}; /*cố định nhãn đỉnh u*/

for ( v ϵ T ) { /*Gán lại nhãn cho các đỉnh trong T*/

if (d[v] > d[u] + A[u,v])

{ d[v] = d[u] + A[u,v]; truoc[v] =u;

}

}

}

}