Module: Ford-Bellman algoritması


Problem

1/6

Ford-Bellman: Başlangıç ​​(C++)

Theory Click to read/hide

Ford-Bellman algoritması
n köşeleri ve m kenarları ve bazı başlangıç ​​köşeleri vG grafiği verilsin > . v köşe noktasından diğer tüm köşelere giden en kısa yolların uzunluklarını bulmak gerekir.

Dijkstra gibi Ford-Bellman 1. köşe ile diğer tüm noktalar arasındaki mesafeyi arar, ancak negatif kenarlarla çalışır güçlü>.
 
Ford-Bellman algoritmasının kendisi birkaç aşamadan oluşur (n-1). Her aşamada, grafiğin tüm kenarları incelenir ve algoritma c maliyetinin her bir kenarı (a, b) boyunca gevşemeye çalışır. Sınır boyunca gevşeme — bu, d[a] 'nin anlamını iyileştirme girişimidir; d[b] + c değeri. Aslında bu, kenar  ve en üstteki geçerli yanıt.

d dizisi, tıpkı Dijkstra'da olduğu gibi, başlangıç ​​köşe noktasından itibaren en kısa uzunlukları içeren bir dizidir, başlangıçta, koymanız gereken başlangıç ​​köşesi dışında mümkün olduğu kadar büyük sayılarla doldururuz. 0.
Kenarları saklamak için bitişiklik matrisi veya ağırlık matrisi değil, kenarın hangi düğümden ayrıldığını (from), nereye geldiğini (to) ve ağırlığı (maliyet).
  yapı kenarı { int from, to, cost; }; vektör<kenar> kenarlar;
INF sabiti "sonsuz" sayısını belirtir - olası tüm yol uzunluklarını açıkça aşacak şekilde seçilmelidir.

Algoritmanın en basit uygulaması: d[v] = 0; için (int i=0; i<n-1; ++i) için (int j=0; j<m; ++j)      if (d[kenarlar[j].from] <INF)        d[kenarlar[j].to] = min(d[kenarlar[j].to], d[kenarlar[j].from] + kenarlar[j].maliyet);

veya C++11 sözdizimini kullanarak biraz daha kısa:
  d[v] = 0; için (int i=0; i< n-1; ++i) için (kenar j: kenarlar) eğer (d[j.from]

İş örneği


Basit yönlendirilmiş bir grafik alın  5 düğüm, 1'e eşit ağırlıkta 4 kenar.

Bu sıradaki kenarların bir listesini sunalım.
4 5 1
3 4 1
2 3 1
1 2 1

En kısa uzunluklar dizisindeki başlangıç ​​değerleri:
 
burada inf, her zaman kenarın ağırlığından büyük olan eşleşen bir tamsayı olmalıdır.

1. geçişten sonra
 
0 bilgi bilgi bilgi bilgi

2. geçişten sonra
 
0 1 bilgi bilgi bilgi

3. geçişten sonra
 
0 1 2 bilgi bilgi


4. geçişten sonra
 
0 1 2 3 bilgi

Kenarları 1'den sona doğru beslersek 1. geçişten sonraki en kısa uzunlukları bulabiliriz.

 

Problem

Aşağıdaki sorunu doğru bir şekilde çözmesi için
programı tamamlayın.

Birden çok kenarı ve döngüsü olabilen yönlendirilmiş bir grafik verildiğinde. Her kenarın bir tamsayı (muhtemelen negatif) olarak ifade edilen bir ağırlığı vardır. Negatif ağırlık döngülerinin olmaması garanti edilir.
1 numaralı köşeden diğer tüm köşelere giden en kısa yolların uzunluklarını hesaplamanız gerekir.
 
Giriş
Program önce N (1 <= N <= 100) sayısını alır – grafik köşelerinin sayısı ve M sayısı (0 <= M <= 10000) – kaburga sayısı. Aşağıdaki satırlar, kenarları tanımlayan üçlü sayılardan M içerir: kenarın başlangıcı, kenarın sonu ve ağırlık (ağırlık - -100 ile 100 arasında bir tamsayıdır).< /div>
 
Çıktı
Program N sayılarını vermelidir – 1 numaralı köşeden grafiğin tüm köşelerine olan mesafeler. Karşılık gelen tepe noktasına giden bir yol yoksa, yolun uzunluğu yerine 30000 sayısını yazdırın.
 
Örnekler
0 1 2 3 4

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++
# Girdi Çıktı
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!