CTDL và giải thuật - Bài tập 2

Bài tập.

Có n thành phố được đánh số từ 1 đến  n. Cho ma trận a thể hiện tính liên thông giữa các thành phố, ví dụ a = [[1, 2], [3, 4]] có nghĩa là:

  • Thành phố 1 và 2 có thể đi đến với nhau với quãng đường là 1.
  • Thành phố 3 và 4 cũng tương tự.

Cho hai số u và v phân biệt. Hãy đưa ra quãng đường ngắn nhất để đi từ thành phố u đến thành phố v. Trả về -1 nếu từ thành phố u không thể đi đến thành phố v.

Ví dụ:

  • Với n = 6, e = [[1,3], [1,2], [2, 3], [3,4], [2,5], [4,6], [6,5], [4,5]], u = 1, v = 5 thì graphFunction(n, e, u, v) = 2.

    Có nhiều cách di chuyển từ thành phố 1 đến 5 những cách nhanh nhất đó là 1 -> 2 -> 5 với quãng đường là 2.
     
  • Với n = 2, e = [[1,2], [3,4]], u = 2, v = 3 thì graphFunction(n, e, u, v) = -1.

Hướng dẫn bài tập.

Với bài này thì cách làm tốt nhất là tìm kiếm theo chiều rộng (Bfs).

Code mẫu:

Ngôn ngữ C++:

bool b[100001];
int c[100001];
bool a[1001][1001];
bool kt = false;
int bfs(int u, int v, int n){
    int kq = n+1;
    queue<int> q;
    q.push(u);
    b[u] = false;
    while(!q.empty()){
        int k = q.front();
        for (int i = 1; i <=n; i++){
            if (a[k][i] && b[i]){
                c[i] = c[k] + 1;
                b[i] = false;
                q.push(i);
                if (i == v) break;
            }
        }
        q.pop();
    }
    return c[v];
}
int graphFunction(int n, std::vector<std::vector<int>> e, int u, int v)
{
    for (int i = 0; i <= n; i++){
        b[i] = true;
        c[i] = 0;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            a[i][j] = false;
        }
    }
    for (int i = 0; i < e.size(); i++){
        a[e[i][0]][e[i][1]] = true;
        a[e[i][1]][e[i][0]] = true;
    }
    int k = bfs(u, v, n);
    return (k == 0) ? -1 : k;
}