Elearning CodePath – CTP Online Judge

🎯 Mục tiêu bài học

Tính đường đi ngắn nhất giữa mọi cặp đỉnh (all-pairs shortest path).
Hiểu vai trò của đỉnh trung gian k trong việc tối ưu hóa đường đi.

📘 Lý thuyết

Floyd–Warshall là thuật toán quy hoạch động: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) với mọi đỉnh trung gian k = 1..n.

💻 Ví dụ Python

INF=10**9
n,m=map(int,input().split())
dist=[[INF]*(n+1) for _ in range(n+1)]
for i in range(1,n+1): dist[i][i]=0
for _ in range(m):
    u,v,w=map(int,input().split())
    dist[u][v]=min(dist[u][v],w)
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
for i in range(1,n+1):
    print(*[x if x





💻 Ví dụ C++
#include 
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    const int INF=1e9;
    vector> dist(n+1,vector(n+1,INF));
    for(int i=1;i<=n;i++) dist[i][i]=0;
    for(int i=0;i>u>>v>>w;
        dist[u][v]=min(dist[u][v],w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<(dist[i][j]==INF?999:dist[i][j])<<" ";
        cout<<"\
";
    }
}



🧩 Bài tập luyện tập

  Tính đường đi ngắn nhất giữa mọi cặp đỉnh.
  Xác định đỉnh có tổng khoảng cách nhỏ nhất tới các đỉnh khác.
  Phát hiện chu trình âm (nếu dist[i][i] < 0).



  💡 Phát hiện chu trình âm
  for i in range(1,n+1):
    if dist[i][i]<0:
        print("Có chu trình âm")