Module: Ford-Bellman-Algorithmus


Problem

1/6

Ford-Bellman: Der Anfang (C++)

Theory Click to read/hide

Algorithm Forda-Bellman
Kann eine konzentrierte Zählung gegeben werden G c) n und m Rippen, und es gibt einen Ausgangspunkt. v♪ Wir müssen die kürzeste Streckenlänge von oben finden. v zu allen anderen Gipfeln.

Genau wie Dextra.Ford-Bellman-Algorithmus Auf der Suche nach einer Entfernung von 1 Top zu allen anderen, aber Arbeiten mit negativen Rippen♪
Ford-Bellmans Algorithmus ist ein paar Phasen.n-1) Alle Zählrippen sind auf jeder Stufe zu untersuchen und der Algorithmus versucht sich entlang jeder Rippe zu entspannen (a, b) Wert c♪ Beziehung entlang der Rippe - es ist ein Versuch, die Bedeutung zu verbessern d[a]Werte d[b] + c♪ In der Tat bedeutet es, dass wir versuchen, die Antwort für die Spitze durch die Verwendung der Rippe und die aktuelle Antwort für die Spitze zu verbessern.

Massiv d - es ist der kürzeste Tauchgang vom Start-up-Peak sowie in Daykstr, der ursprünglich mit möglichst vielen Zahlen gefüllt ist, abgesehen vom Start-up-Top, wo Null gesetzt werden muss.
Die Rippen werden nicht von der benachbarten Matrix oder der Gewichtsmatrix verwendet, sondern von der Liste, aus der die Rippe freigegeben wird (die Liste).fromIn diesem Falltound sein Gewichtcost)
Strebekante {
von, zu, Kosten;
?
vektorausgestrahlte Teilkanten;

konstant INF Beschreibt die Anzahl der "Ausdauer" - es muss so erhalten werden, dass es alle möglichen Längen deutlich überschreitet.

Einfache Implementierung des Algorithmus: 
d[v] = 0;
für (int i=0; i Visitn-1; ++i)
für (int j=0; j Visitm; ++j)
wenn (d[edges[j].from] PER INF)
d[edges[j].to] = min (d[edges[j].to], d[edges[j].from] + edge[j].cost);

oder etwas kürzer mit Kunststoffen C++11:
d[v] = 0;
für (int i=0; iς n-1; ++i)
für (Schlitten j: Kanten)
wenn (d[j.from] Ø INF)
d[j.to] = min (d[j.to], d[j.aus] + j.cost);

Beispiel der Arbeit


Wir nehmen ein einfaches Ohr mit 5 Knoten, 4. Rippen wiegen 1.

Wir setzen die Rippenliste in diese Reihenfolge.
4 5 1
3 4 1
Artikel 2
1 2 1

Referenzwerte im kürzesten Bereich:
0)infinfinfinf

wobei Inf eine solche ganze Zahl sein soll, die immer größer als das Rippengewicht wäre.

Nach dem 1. Durchgang
0)1infinfinf

Nach 2. Durchgang
0)12infinf

Nach 3. Pass
0)123inf


Nach 4. Durchgang
0)123ANHANG

Wenn wir die Rippen in Ordnung bringen würden, könnten wir die kürzeste Länge nach dem 1. Durchgang finden.

Problem

Ergänzen Sie das Programm, damit es die nächste Aufgabe richtig löst.

Es wird ein orientiertes Diagramm gegeben, das mehrere Kanten und Schleifen enthalten kann. Jede Kante hat ein Gewicht, das durch eine ganze Zahl ausgedrückt wird (möglicherweise negativ). Es ist garantiert, dass es keine negativen Gewichtszyklen gibt.
Sie müssen die Längen der kürzesten Pfade vom Scheitelpunkt Nummer 1 bis zu allen anderen Scheitelpunkten berechnen.
 
Eingabe
Das Programm erhält zuerst die Zahl N (1 <= N <= 100) – die Anzahl der Eckpunkte des Graphen und die Anzahl der M (0 <= M <= 10000) – die Anzahl der Kanten. In den folgenden Zeilen gibt es M drei Zahlen, die die Kanten beschreiben: den Anfang der Kante, das Ende der Kante und das Gewicht (das Gewicht ist eine ganze Zahl von -100 bis 100).
 
Ausgabe
Das Programm sollte N Zahlen – die Entfernung vom Scheitelpunkt Nummer 1 zu allen Scheitelpunkten des Graphen ausgeben. Wenn kein Pfad zum entsprechenden Scheitelpunkt vorhanden ist, geben Sie anstelle der Pfadlänge die Zahl 30.000 aus.
 
Beispiele
№ Eingabe Ausgabe
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!