Mình post thử thuật toán tìm đường đi dài nhất mọi người xem thử có đúng không nhé.
tìm đường đi dài nhất từ s đến t. d(x) là đường đi dài nhất từ s đến x. a(u,x) là trọng số của cạnh có đỉnh là đỉnh đã duyệt cuối cùng (giả sử là u) và x.

Tư tưởng là dùng Dijkstra nhưng có chút thay đổi. thay vì khởi tạo ban đầu d(x) = vô cùng thì khởi tạo ban đầu là d(x)=0.

Thuật toán:

với mỗi đỉnh x thì đặt d(x) = 0
finish = false;
while (!finish)
    {
    finish = true;
    với mỗi đỉnh v của đồ thị
        {
            if( d(u) + a(u,v) > d(v))
              { d(v) = d(u) + a(u,v); finish = false;}
        loại đỉnh v ra khỏi tập đỉnh đang xét
          }

    }