Bellman Fordin algoritmi

Bellman Fordin algoritmi auttaa meitä löytämään lyhimmän polun pisteestä painotetun kuvaajan kaikkiin muihin pisteisiin.

Se on samanlainen kuin Dijkstran algoritmi, mutta se voi toimia graafien kanssa, joissa reunojen paino voi olla negatiivinen.

Miksi todellisessa elämässä olisi koskaan negatiivisia painoja?

Negatiiviset painoreunat saattavat vaikuttaa aluksi hyödyttömiltä, mutta ne voivat selittää monia ilmiöitä, kuten kassavirta, kemiallisessa reaktiossa vapautuva / absorboitunut lämpö jne.

Esimerkiksi jos on olemassa erilaisia tapoja päästä yhdestä kemikaalista A toiseen kemikaaliin B, kullakin menetelmällä on alireaktioita, joihin liittyy sekä lämmöntuotto että absorptio.

Jos haluamme löytää joukon reaktioita, joissa vaaditaan vähimmäisenergiaa, meidän on kyettävä ottamaan huomioon lämmön absorptio negatiivisina painoina ja lämmön haihtuminen positiivisina painoina.

Miksi meidän on oltava varovaisia negatiivisten painojen kanssa?

Negatiiviset painoreunat voivat luoda negatiivisia painojaksoja eli jakson, joka vähentää kokonaispolun etäisyyttä palaamalla samaan pisteeseen.

Negatiiviset painosyklit voivat antaa virheellisen tuloksen yrittäessään selvittää lyhintä polkua

Lyhyimmät polkualgoritmit, kuten Dijkstran algoritmit, jotka eivät pysty havaitsemaan tällaista sykliä, voivat antaa virheellisen tuloksen, koska ne voivat käydä läpi negatiivisen painojakson ja vähentää polun pituutta.

Kuinka Bellman Fordin algoritmi toimii

Bellman Fordin algoritmi toimii yliarvioimalla polun pituuden alkupisteestä muihin pisteisiin. Sitten se rentouttaa nämä arviot iteratiivisesti löytämällä uusia polkuja, jotka ovat lyhyempiä kuin aiemmin yliarvioidut polut.

Tekemällä tämän toistuvasti kaikille pisteille voimme taata, että tulos on optimoitu.

Step-1 Bellman Fordin algoritmille

Step-2 Bellman Fordin algoritmille

Step-3 Bellman Fordin algoritmille

Step-4 Bellman Fordin algoritmille

Step-5 Bellman Fordin algoritmille Step-5 Bellman Fordin algoritmille Step-5 Bellman Fordin algoritmille

Step-6 Bellman Fordin algoritmille

Bellman Ford Pseudocode

Meidän on säilytettävä jokaisen kärjen polkuetäisyys. Voimme tallentaa sen matriisiin, jonka koko on v, jossa v on kärkipisteiden lukumäärä.

Haluamme myös pystyä saamaan lyhimmän polun, emmekä tiedä vain lyhimmän polun pituutta. Tätä varten kartoitetaan jokainen kärki siihen kärkeen, joka viimeksi päivitti polun pituuden.

Kun algoritmi on ohi, voimme palata kohdepisteestä lähdepisteeseen polun löytämiseksi.

 funktio bellmanFord (G, S) jokaiselle kärjelle V G-etäisyydellä (V) <- ääretön edellinen (V) <- NULL-etäisyys (S) <- 0 jokaiselle kärjelle V G: ssä jokaiselle reunalle (U, V) G tempDistance <- etäisyys (U) + reunapaino (U, V) jos tempDistance <etäisyys (V) etäisyys (V) <- tempDistance edellinen (V) <- U jokaiselle reunalle (U, V) G Jos etäisyys (U) + reunapaino (U, V) <etäisyys (V) Virhe: Negatiivinen sykli olemassa paluumatka (), edellinen ()

Bellman Ford vs Dijkstra

Bellman Fordin algoritmi ja Dijkstran algoritmi ovat rakenteeltaan hyvin samanlaisia. Vaikka Dijkstra näyttää vain kärjen välittömille naapureille, Bellman kulkee jokaisen reunan läpi jokaisessa iteraatiossa.

Dijkstran vs Bellman Fordin algoritmi

Python-, Java- ja C / C ++ -esimerkkejä

Python Java C C ++

 # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)

 // Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )

 // Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )

 // Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )

Bellman Fordin monimutkaisuus

Ajan monimutkaisuus

Parhaan tapauksen monimutkaisuus	O (E)
Keskimääräinen tapauksen monimutkaisuus	O (VE)
Pahimman tapauksen monimutkaisuus	O (VE)

Avaruuden monimutkaisuus

Ja avaruuden monimutkaisuus on O(V).