Giải thuật - Single-Source Shortest Paths

ª Bài toán các đường đi ngắn nhất: một số thuật ngữ.
Cho một đồ thị có trọng số, có hướng G = (V, E), với một hàm trọng số w : E -R
– Trọng số của một đường đi p = v0 , v1,…, vk ?
• w(p) = i = 1…k w(vi? 1 , vi )
– Trọng số của đường đi ngắn nhất (shortest path weight) từ u đến v
min{w(p) : u v } nếu có đường đi từ u đến v
? các trường hợp khác
– Đường đi ngắn nhất từ u đến v là bất kỳ đường đi p nào từ u đến v sao cho w(p) = d(u, v).