Tóm tắt đề bài: Cho đồ thị vô hướng liên thông G = (V, E), |V| = n, |E| = m. Đồ thị G có ít nhất một cạnh cầu. Cho hai đỉnh s và t, tìm thời gian nhỏ nhất để đi từ (s, t) tới (u, v) với (u, v) là hai đỉnh của một cạnh cầu bất kỳ trong G.

Ban đầu, ta sử dụng thuật toán Dijkstra để tính đường đi ngắn nhất từ đỉnh s và đỉnh t tới các đỉnh còn lại trong G.

Sau đó, ta đi tìm tất cả các cạnh (u, v) là cầu của đồ thị G. Thời gian nhỏ nhất để đi từ (s, t) tới (u, v) được tính theo công thức sau :

• t₁ = max(dist_s[u], dist_t[v])
• t₂ = max(dist_s[v], dist_t[u])
• time_{(u, v)} = min(t₁, t₂)

Đáp án là min(time_{(u, v)}) với (u, v) là cạnh cầu của G

Độ phức tạp: ~\mathcal{O}(nlogn)~. Code tham khảo