Problem

1/6

فورد بيلمان: البداية (C ++)

Theory Click to read/hide

خوارزمية Ford-Bellman
لنحصل على رسم بياني مرجح موجه G برؤوس n وحواف m ، وبعض رؤوس البداية v . مطلوب إيجاد أطوال أقصر المسارات من الرأس v إلى جميع الرؤوس الأخرى.

مثل Dijkstra ، تبحث Ford-Bellman عن المسافة من قمة الرأس 1 إلى جميع العناصر الأخرى ، ولكن تعمل مع الحواف السالبة .
نبسب ؛
تتكون خوارزمية Ford-Bellman نفسها من عدة مراحل ( n-1 ). في كل مرحلة ، يتم فحص جميع حواف الرسم البياني ، وتحاول الخوارزمية الاسترخاء على طول كل حافة (أ ، ب) من التكلفة ج . الاسترخاء على طول الحافة & [مدش]؛ هذه محاولة لتحسين معنى d [a] & nbsp؛ القيمة d [b] + c . في الواقع ، هذا يعني أننا نحاول تحسين إجابة الرأس باستخدام الحافة & nbsp؛ والجواب الحالي لأعلى.

المصفوفة d هي مصفوفة من أقصر الأطوال من قمة البداية ، تمامًا كما هو الحال في Dijkstra ، نملأها في البداية بأكبر عدد ممكن ، باستثناء قمة البداية ، التي تحتاج إلى وضعها 0.
لتخزين الحواف ، لا يتم استخدام مصفوفة متجاورة أو مصفوفة وزن ، ولكن قائمة تشير إلى أي عقدة تترك الحافة ( من ) ، والتي تأتي إليها ( إلى ) ووزنها ( cost ).
نبسب ؛ حافة الهيكل { int من ، إلى ، تكلفة ؛ } ؛ ناقلات العلامة & lt ؛ حافة & GT ؛ حواف؛
يشير ثابت INF إلى الرقم "اللانهاية" - يجب اختياره بطريقة تتجاوز بوضوح جميع أطوال المسار الممكنة.

أبسط تطبيق للخوارزمية: د [v] = 0 ؛ لـ (int i = 0 ؛ i & lt ؛ n-1 ؛ ++ i) لـ (int j = 0 ؛ j & lt ؛ m ؛ ++ j) نبسب ؛ نبسب ؛ نبسب ؛ إذا (د [حواف [ي]. من] & lt؛ INF) نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ د [حواف [ي]. إلى] = دقيقة (د [حواف [ي]. إلى] ، د [حواف [ي]. من] + حواف [ي]. تكلفة) ؛

أو أقصر قليلاً باستخدام بناء الجملة C ++ 11 :
نبسب ؛ د [v] = 0 ؛ لـ (int i = 0 ؛ i & lt ؛ n-1 ؛ ++ i) لـ (edge ​​j: edges) إذا (d [j.from] & lt؛ INF) d [j.to] = min (d [j.to]، d [j.from] + j.cost) ؛

مثال العمل

خذ رسمًا بيانيًا بسيطًا موجهًا & nbsp؛ مع 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

بعد التمريرة الثانية
نبسب ؛ <الجسم>
0 1 2 inf inf

بعد التمريرة الثالثة
نبسب ؛ <الجسم>
0 1 2 3 inf


بعد الممر الرابع
نبسب ؛ <الجسم>
0 1 2 3 4

إذا قمنا بتغذية الحواف بالترتيب من 1 إلى الأخير ، فيمكننا إيجاد أقصر أطوال بعد التمريرة الأولى.

نبسب ؛

Problem

أكمل البرنامج حتى يحل المشكلة التالية بشكل صحيح.

إعطاء رسم بياني موجه يمكن أن يكون له حواف وحلقات متعددة. كل حافة لها وزن معبر عنه بعدد صحيح (ربما سالب). ويضمن عدم وجود دورات وزن سلبية.
أنت بحاجة إلى حساب أطوال أقصر المسارات من الرأس رقم 1 إلى جميع الرؤوس الأخرى.
& nbsp؛
إدخال
يتلقى البرنامج أولاً الرقم N (1 & lt؛ = N & lt؛ = 100) & ndash؛ عدد رؤوس الرسم البياني والرقم M (0 & lt؛ = M & lt؛ = 10000) & ndash؛ عدد الضلوع. تحتوي الأسطر التالية على M من ثلاثة أرقام تصف الحواف: بداية الحافة ، ونهاية الحافة ، والوزن (الوزن & ndash ؛ هو عدد صحيح من -100 إلى 100). < / div>
& nbsp؛
الإخراج
يجب على البرنامج إخراج أرقام N & ndash؛ المسافات من الرأس رقم 1 إلى جميع رؤوس الرسم البياني. إذا لم يكن هناك مسار للرأس المقابل ، فقم بطباعة الرقم 30000 بدلاً من طول المسار.
نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1
6 4
1 2 10
2 3 10
1 3100
4 5-10
0 10 20 30000 30000 30000 & nbsp؛

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!