Module: Thuật toán Ford-Bellman


Problem

1/6

Ford-Bellman: Sự khởi đầu (C++)

Theory Click to read/hide

Thuật toán Ford-Bellman
Hãy cho một đồ thị có trọng số trực tiếp G với các đỉnh n và các cạnh m và một số đỉnh bắt đầu v . Cần tìm độ dài của các đường đi ngắn nhất từ ​​đỉnh v đến tất cả các đỉnh khác.

Giống như Dijkstra, Ford-Bellman tìm kiếm khoảng cách từ đỉnh 1 đến tất cả các đỉnh khác, nhưng hoạt động với các cạnh âm.
 
Bản thân thuật toán Ford-Bellman bao gồm một số giai đoạn (n-1). Ở mỗi giai đoạn, tất cả các cạnh của biểu đồ đều được kiểm tra và thuật toán sẽ cố gắng thư giãn dọc theo từng cạnh (a, b) của chi phí c. Thư giãn dọc theo bờ vực — đây là một nỗ lực để cải thiện ý nghĩa của d[a]  giá trị d[b] + c. Trên thực tế, điều này có nghĩa là chúng tôi đang cố gắng cải thiện câu trả lời cho đỉnh bằng cách sử dụng cạnh  và câu trả lời hiện tại cho top.

Mảng d là một mảng có độ dài ngắn nhất tính từ đỉnh bắt đầu, giống như trong Dijkstra, ban đầu chúng ta điền nó với số lượng lớn nhất có thể, ngoại trừ đỉnh bắt đầu mà bạn cần đặt 0.
Để lưu trữ các cạnh, không sử dụng ma trận kề hoặc ma trận trọng số mà sử dụng một danh sách cho biết cạnh rời khỏi nút nào (từ), nơi nó đến (đến) và trọng số của nó (chi phí).
  cạnh cấu trúc { int from, to, cost; }; vectơ<cạnh> cạnh;
Hằng số INF biểu thị số "vô cực" - nó phải được chọn theo cách rõ ràng vượt quá tất cả các độ dài đường dẫn có thể có.

Việc thực hiện đơn giản nhất của thuật toán: d[v] = 0; cho (int i=0; i<n-1; ++i) cho (int j=0; j<m; ++j)      nếu (d[cạnh[j].từ] <INF)        d[edges[j].to] = min(d[edges[j].to], d[edges[j].from] + Edges[j].cost);

hoặc ngắn hơn một chút bằng cú pháp C++11:
  d[v] = 0; cho (int i=0; i< n-1; ++i) cho (cạnh j: các cạnh) nếu (d[j.từ] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

Ví dụ công việc


Lấy một đồ thị có hướng đơn giản  với 5 nút, 4 cạnh có trọng số bằng 1.

Hãy giới thiệu một danh sách các cạnh theo thứ tự đó.
4 5 1
3 4 1
2 3 1
1 2 1

Các giá trị ban đầu trong mảng có độ dài ngắn nhất:
 
trong đó inf phải là một số nguyên khớp luôn lớn hơn trọng số của cạnh.

Sau lần đầu tiên
 
0 inf inf inf inf

Sau lần thứ 2
 
0 1 inf inf inf

Sau lần thứ 3
 
0 1 2 inf inf


Sau lần thứ 4
 
0 1 2 3 inf

Nếu chúng tôi cung cấp các cạnh theo thứ tự từ 1 đến cuối cùng, chúng tôi có thể tìm thấy độ dài ngắn nhất sau lần chạy đầu tiên.

 

Problem

Hoàn thành chương trình để chương trình giải đúng bài toán sau.

Cho một đồ thị có hướng có thể có nhiều cạnh và nhiều vòng. Mỗi cạnh có trọng số được biểu thị dưới dạng số nguyên (có thể âm). Chúng tôi đảm bảo rằng không có chu kỳ trọng lượng âm.
Bạn cần tính độ dài của các đường đi ngắn nhất từ ​​đỉnh số 1 đến tất cả các đỉnh khác.
 
Đầu vào
Đầu tiên, chương trình nhận số N (1 <= N <= 100) – số đỉnh của đồ thị và số M (0 <= M <= 10000) – số lượng xương sườn. Các dòng sau chứa M trong bộ ba số mô tả các cạnh: đầu cạnh, cuối cạnh và trọng số (trọng số – là một số nguyên từ -100 đến 100).< /div>
 
Đầu ra
Chương trình sẽ xuất ra N số – khoảng cách từ đỉnh số 1 đến tất cả các đỉnh của đồ thị. Nếu không có đường đi đến đỉnh tương ứng, hãy in số 30000 thay vì độ dài của đường đi.
 
Ví dụ
0 1 2 3 4
<đầu>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Đầu vào Đầu ra
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!