Module: الگوریتم فورد-بلمن


Problem

1/6

Ford-Bellman: The Beginning (C++)

Theory Click to read/hide

الگوریتم فورد-بلمن
اجازه دهید یک نمودار وزنی جهت دار G با راس n و یال های m و مقداری راس شروع v لازم است طول کوتاهترین مسیرها از راس v تا همه رئوس دیگر را پیدا کنید.

مانند Dijkstra، Ford-Bellman به دنبال فاصله از راس 1 تا سایر موارد است، اما با لبه های منفی کار می کند.
 
الگوریتم فورد-بلمن خود از چند مرحله تشکیل شده است (n-1). در هر مرحله، تمام لبه‌های نمودار بررسی می‌شوند و الگوریتم سعی می‌کند در امتداد هر یال (a, b) هزینه c آرام شود. آرامش در امتداد لبه — این تلاشی است برای بهبود معنای d[a]  مقدار d[b] + c. در واقع این بدان معناست که ما سعی داریم با استفاده از edge  و پاسخ فعلی برای بالا.

آرایه d آرایه‌ای از کوتاه‌ترین طول‌ها از راس شروع است، درست مانند Dijkstra، در ابتدا آن را با حداکثر تعداد ممکن پر می‌کنیم، به جز راس شروع، که باید در آن قرار دهید. 0.
برای ذخیره یال‌ها، از ماتریس مجاورت یا ماتریس وزن استفاده نمی‌شود، بلکه از فهرستی استفاده می‌شود که نشان می‌دهد لبه از کدام گره خارج می‌شود (from)، که به آن می‌آید (to) و وزن آن (هزینه).
  لبه ساختار { int from, to, cost; }; بردار<لبه> لبه ها؛
ثابت INF نشان دهنده عدد "بی نهایت" است. - باید به گونه ای انتخاب شود که آشکارا از تمام طول مسیرهای ممکن تجاوز کند.

ساده ترین پیاده سازی الگوریتم: d[v] = 0; برای (int i=0; i<n-1; ++i) برای (int j=0; j<m; ++j)      if (d[ لبه‌ها[j].from] <INF)        d[لبه[j].to] = min(d[لبه[j].to], d[لبه[j].from] + یال[j].cost);

یا کمی کوتاهتر با استفاده از نحو C++11:
  d[v] = 0; برای (int i=0; i< n-1; ++i) برای (لبه j: لبه ها) اگر (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

نمونه کار


یک نمودار جهت دار ساده بگیرید  با 5 گره، 4 یال با وزن برابر 1.

بیایید لیستی از لبه ها را به ترتیب معرفی کنیم.
4 5 1
3 4 1
2 3 1
1 2 1

مقادیر اولیه در آرایه های کوتاه ترین طول ها:
  <بدن>
0 inf inf inf inf

که در آن inf باید یک عدد صحیح منطبق باشد که همیشه از وزن یال بزرگتر است.

پس از اولین پاس
  <بدن>
0 1 inf inf inf

بعد از پاس 2
  <بدن>
0 1 2 inf inf

بعد از پاس سوم
  <بدن>
0 1 2 3 inf


بعد از پاس چهارم
  <بدن>
0 1 2 3 4

اگر لبه‌ها را به ترتیب از 1 تا آخر تغذیه کنیم، می‌توانیم کوتاه‌ترین طول‌ها را پس از پاس اول پیدا کنیم.

 

Problem

برنامه را تکمیل کنید تا مشکل زیر را به درستی حل کند.

یک نمودار جهت دار داده می شود که می تواند چندین لبه و حلقه داشته باشد. هر یال دارای وزنی است که به صورت یک عدد صحیح بیان می شود (احتمالاً منفی). تضمین شده است که هیچ چرخه وزن منفی وجود ندارد.
شما باید طول کوتاه ترین مسیرها را از راس شماره 1 تا همه رئوس دیگر محاسبه کنید.
 
ورودی
برنامه ابتدا عدد N (1 <= N <= 100) – تعداد رئوس نمودار و عدد M (0 <= M <= 10000) – تعداد دنده ها خطوط زیر شامل M از سه عدد از اعداد است که لبه‌ها را توصیف می‌کنند: ابتدای یال، انتهای لبه و وزن (وزن – یک عدد صحیح از 100- تا 100 است).< /div>
 
خروجی
برنامه باید اعداد N – فاصله از راس شماره 1 تا تمام رئوس نمودار. اگر مسیری به راس مربوطه وجود ندارد، به جای طول مسیر، عدد 30000 را چاپ کنید.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 

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++
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!