Imaginați-vă că aveți o hartă cu diferite orașe conectate prin drumuri, fiecare drum având o anumită distanță. The Algoritmul Bellman-Ford este ca un ghid care te ajută să găsești cea mai scurtă cale de la un oraș la toate celelalte orașe, chiar dacă unele drumuri au lungimi negative. Este ca o GPS pentru computere, util pentru a descoperi cea mai rapidă modalitate de a ajunge de la un punct la altul într-o rețea. În acest articol, vom arunca o privire mai atentă asupra modului în care funcționează acest algoritm și de ce este atât de util în rezolvarea problemelor de zi cu zi.
Cuprins
- Algoritmul Bellman-Ford
- Ideea din spatele algoritmului Bellman Ford
- Principiul relaxării marginilor pentru Bellman-Ford
- De ce Relaxing Edges de N-1 ori, ne oferă o singură sursă cea mai scurtă cale?
- De ce reducerea distanței în cea de-a N-a relaxare indică existența unui ciclu negativ?
- Funcționarea algoritmului Bellman-Ford pentru a detecta ciclul negativ în grafic
- Algoritm pentru a găsi ciclul negativ într-un grafic ponderat direcționat folosind Bellman-Ford
- Gestionarea graficelor deconectate în algoritm
- Analiza complexității algoritmului Bellman-Ford
- Aplicațiile algoritmului Bellman Ford
- Dezavantajul algoritmului lui Bellman Ford
Algoritmul Bellman-Ford
Bellman-Ford este o singura sursa algoritmul de calea cea mai scurtă care determină calea cea mai scurtă între un punct sursă dat și fiecare alt vârf dintr-un grafic. Acest algoritm poate fi folosit pe ambele ponderat și neponderat grafice.
variabile nginx
A Bellman-Ford algoritmul este, de asemenea, garantat pentru a găsi calea cea mai scurtă într-un grafic, similar cu algoritmul lui Dijkstra . Deși Bellman-Ford este mai lent decât algoritmul lui Dijkstra , este capabil să manipuleze grafice cu greutățile marginii negative , ceea ce îl face mai versatil. Cea mai scurtă cale nu poate fi găsită dacă există a ciclu negativ în grafic. Dacă continuăm să ocolim ciclul negativ de un număr infinit de ori, atunci costul căii va continua să scadă (chiar dacă lungimea căii este în creștere). Ca urmare, Bellman-Ford este, de asemenea, capabil să detecteze cicluri negative , care este o caracteristică importantă.
Ideea din spatele algoritmului Bellman Ford:
Principiul principal al algoritmului Bellman-Ford este că începe cu o singură sursă și calculează distanța până la fiecare nod. Distanța este inițial necunoscută și se presupune că este infinită, dar pe măsură ce timpul trece, algoritmul relaxează acele căi identificând câteva căi mai scurte. De aceea se spune că se bazează Bellman-Ford Principiul Relaxării .
Principiul relaxării marginilor pentru Bellman-Ford:
- Afirmă că pentru graficul având N vârfuri, toate marginile ar trebui să fie relaxate N-1 ori pentru a calcula calea cea mai scurtă sursă unică.
- Pentru a detecta dacă există sau nu un ciclu negativ, relaxați toată marginea încă o dată și dacă cea mai scurtă distanță pentru orice nod se reduce atunci putem spune că există un ciclu negativ. Pe scurt dacă relaxăm marginile N ori și există vreo modificare în cea mai scurtă distanță a oricărui nod între N-1 și Nth relaxare decât un ciclu negativ există, altfel nu există.
De ce Relaxing Edges de N-1 ori, ne oferă o singură sursă cea mai scurtă cale?
În cel mai rău caz, o cale cea mai scurtă între două vârfuri poate avea cel mult N-1 margini, unde N este numărul de vârfuri. Acest lucru se datorează faptului că o cale simplă într-un grafic cu N vârfurile pot avea cel mult N-1 margini, deoarece este imposibil să se formeze o buclă închisă fără a revedea un vârf.
Prin relaxarea marginilor N-1 de ori, algoritmul Bellman-Ford asigură că estimările distanței pentru toate nodurile au fost actualizate la valorile lor optime, presupunând că graficul nu conține niciun ciclu de greutate negativă accesibil de la vârful sursă. Dacă un grafic conține un ciclu cu greutate negativă accesibil de la vârful sursă, algoritmul îl poate detecta după N-1 iterații, deoarece ciclul negativ perturbă cele mai scurte lungimi de drum.
Pe scurt, margini relaxante N-1 ori în algoritmul Bellman-Ford garantează că algoritmul a explorat toate căile posibile de lungime până la N-1 , care este lungimea maximă posibilă a unei căi cele mai scurte dintr-un grafic cu N vârfuri. Acest lucru permite algoritmului să calculeze corect cele mai scurte căi de la vârful sursă la toate celelalte vârfuri, având în vedere că nu există cicluri cu greutate negativă.
De ce reducerea distanței în cea de-a N-a relaxare indică existența unui ciclu negativ?
După cum s-a discutat anterior, este nevoie de realizarea celei mai scurte căi către toate celelalte noduri N-1 relaxări. Dacă relaxarea a N-a reduce și mai mult distanța cea mai scurtă pentru orice nod, înseamnă că o anumită muchie cu greutate negativă a fost traversată încă o dată. Este important de reținut că în timpul N-1 relaxări, am presupus că fiecare vârf este parcurs o singură dată. Cu toate acestea, reducerea distanței în timpul relaxării N’ indică revederea unui vârf.
Funcționarea algoritmului Bellman-Ford pentru a detecta ciclul negativ în grafic:
Să presupunem că avem un grafic care este prezentat mai jos și dorim să aflăm dacă există un ciclu negativ sau nu folosind Bellman-Ford.
Graficul inițial
Pasul 1: Inițializați o matrice de distanțe Dist[] pentru a stoca cea mai scurtă distanță pentru fiecare vârf de la vârful sursă. Inițial, distanța sursei va fi 0 și Distanța altor vârfuri va fi INFINITY.
Inițializați o matrice de distanțe
tutorial java jfxPasul 2: Începeți să relaxați marginile, în timpul primei relaxări:
straturi model osi
- Distanța curentă a lui B> (Distanța lui A) + (Greutatea lui A la B), adică infinit> 0 + 5
- Prin urmare, Dist[B] = 5
1 Relaxare
Pasul 3: În timpul celei de-a doua relaxări:
- Distanța curentă a lui D> (Distanța lui B) + (Greutatea lui B la D), adică Infinitul> 5 + 2
- Dist[D] = 7
- Distanța curentă a lui C> (Distanța lui B) + (Greutatea lui B la C), adică Infinitul> 5 + 1
- Dist[C] = 6
a 2-a relaxare
Pasul 4: În timpul celei de-a treia relaxări:
- Distanța curentă de F> (Distanța de D ) + (Greutatea de la D la F), adică Infinitul> 7 + 2
- Dist[F] = 9
- Distanța curentă a lui E> (Distanța lui C ) + (Greutatea lui C la E), adică Infinitul> 6 + 1
- Dist[E] = 7
a 3-a Relaxare
Pasul 5: În timpul celei de-a patra relaxări:
- Distanța curentă a lui D> (Distanța lui E) + (Greutatea lui E la D), adică 7> 7 + (-1)
- Dist[D] = 6
- Distanța curentă a lui E> (Distanța lui F) + (Greutatea lui F la E), adică 7> 9 + (-3)
- Dist[E] = 6
a 4-a Relaxare
Pasul 6: În timpul celei de-a 5-a relaxări:
- Distanța curentă de F> (Distanța de D) + (Greutatea de la D la F), adică 9> 6 + 2
- Dist[F] = 8
- Distanța curentă a lui D> (Distanța lui E) + (Greutatea lui E la D), adică 6> 6 + (-1)
- Dist[D] = 5
- Deoarece graficul h 6 vârfuri, deci în timpul celei de-a 5-a relaxări ar fi trebuit calculată cea mai scurtă distanță pentru toate vârfurile.
a 5-a Relaxare
Pasul 7: Acum, relaxarea finală, adică a șasea relaxare, ar trebui să indice prezența ciclului negativ dacă există modificări în matricea distanțelor a cincea relaxare.
În timpul celei de-a 6-a relaxări, pot fi observate următoarele modificări:
- Distanța curentă de E> (Distanța de F) + (Greutatea de la F la E), adică 6> 8 + (-3)
- Dist[E]=5
- Distanța curentă de F> (Distanța de D ) + (Greutatea de la D la F), adică 8> 5 + 2
- Dist[F]=7
Deoarece observăm schimbări în matricea Distanță Prin urmare, putem concluziona prezența unui ciclu negativ în grafic.
a 6-a Relaxare
hartă javaRezultat: Un ciclu negativ (D->F->E) există în grafic.
Algoritm pentru a găsi ciclul negativ într-un grafic ponderat direcționat folosind Bellman-Ford:
- Inițializați matricea de distanțe dist[] pentru fiecare vârf ‘ în ' la fel de dist[v] = INFINITATE .
- Presupuneți orice vârf (să spunem „0”) ca sursă și atribuiți dist = 0 .
- Relaxează-te pe toate muchii (u,v,greutate) N-1 ori conform condiției de mai jos:
- dist[v] = minim(dist[v], distanță[u] + greutate)
- Acum, relaxați-vă toate marginile încă o dată, adică Nth timp și pe baza celor două cazuri de mai jos putem detecta ciclul negativ:
- Cazul 1 (ciclul negativ există): Pentru oricare margine (u, v, greutate), dacă dist[u] + greutate
- Cazul 2 (Fără ciclu negativ): cazul 1 eșuează pentru toate marginile.
- Cazul 1 (ciclul negativ există): Pentru oricare margine (u, v, greutate), dacă dist[u] + greutate
Gestionarea graficelor deconectate în algoritm:
Algoritmul și programul de mai sus ar putea să nu funcționeze dacă graficul dat este deconectat. Funcționează atunci când toate nodurile sunt accesibile de la vârful sursă 0 .
Pentru a gestiona graficele deconectate, putem repeta algoritmul de mai sus pentru nodurile care au distanta = INFINIT, sau pur și simplu pentru vârfurile care nu sunt vizitate.
Mai jos este implementarea abordării de mai sus:
C++ // A C++ program for Bellman-Ford's single source // shortest path algorithm. #include using namespace std; // a structure to represent a weighted edge in graph struct Edge { int src, dest, weight; }; // a structure to represent a connected, directed and // weighted graph struct Graph { // V->Număr de vârfuri, E-> Număr de muchii int V, E; // graficul este reprezentat ca o matrice de muchii. struct Edge* margine; }; // Creează un grafic cu V vârfuri și E muchii struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph; grafic->V = V; grafic->E = E; graph->edge = margine nouă[E]; graficul de întoarcere; } // O funcție de utilitate folosită pentru a tipări soluția void printArr(int dist[], int n) { printf('Vertex Distance from Source
'); pentru (int i = 0; i< n; ++i) printf('%d %d
', i, dist[i]); } // The main function that finds shortest distances from src // to all other vertices using Bellman-Ford algorithm. The // function also detects negative weight cycle void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = graph->E; int dist[V]; // Pasul 1: Inițializați distanțele de la src la toate celelalte // vârfuri ca INFINIT pentru (int i = 0; i< V; i++) dist[i] = INT_MAX; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can have // at-most |V| - 1 edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->margine[j].src; int v = graph->edge[j].dest; int greutate = graph->edge[j].greutate; dacă (dist[u] != INT_MAX && dist[u] + greutate< dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The above // step guarantees shortest distances if graph doesn't // contain negative weight cycle. If we get a shorter // path, then there is a cycle. for (int i = 0; i < E; i++) { int u = graph->margine[i].src; int v = graph->edge[i].dest; int greutate = graph->edge[i].greutate; dacă (dist[u] != INT_MAX && dist[u] + greutate< dist[v]) { printf('Graph contains negative weight cycle'); return; // If negative cycle is detected, simply // return } } printArr(dist, V); return; } // Driver's code int main() { /* Let us create the graph given in above example */ int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph struct Graph* graph = createGraph(V, E); // add edge 0-1 (or A-B in above figure) graph->margine[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].greutate = -1; // adaugă muchia 0-2 (sau A-C în figura de mai sus) graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].greutate = 4; // adăugați muchia 1-2 (sau B-C în figura de mai sus) graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].greutate = 3; // adaugă muchia 1-3 (sau B-D în figura de mai sus) graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].greutate = 2; // adăugați muchia 1-4 (sau B-E în figura de mai sus) graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].greutate = 2; // adăugați muchia 3-2 (sau D-C în figura de mai sus) graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].greutate = 5; // adăugați muchia 3-1 (sau D-B în figura de mai sus) graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].greutate = 1; // adăugați muchia 4-3 (sau E-D în figura de mai sus) graph->edge[7].src = 4; graph->edge[7].dest = 3; grafic->margine[7].greutate = -3; // Apel de funcție BellmanFord(graph, 0); întoarce 0; }>>>Java Python3 # Python3 program for Bellman-Ford's single source # shortest path algorithm. # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print('Vertex Distance from Source') for i in range(self.V): print('{0} {1}'.format(i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float('Inf')] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for _ in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: print('Graph contains negative weight cycle') return # print all distance self.printArr(dist) # Driver's code if __name__ == '__main__': g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # function call g.BellmanFord(0) # Initially, Contributed by Neelam Yadav # Later On, Edited by Himanshu Garg> C# // C# program for Bellman-Ford's single source shortest // path algorithm. using System; // A class to represent a connected, directed and weighted // graph class Graph { // A class to represent a weighted edge in graph class Edge { public int src, dest, weight; public Edge() { src = dest = weight = 0; } }; int V, E; Edge[] edge; // Creates a graph with V vertices and E edges Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } // The main function that finds shortest distances from // src to all other vertices using Bellman-Ford // algorithm. The function also detects negative weight // cycle void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int[] dist = new int[V]; // Step 1: Initialize distances from src to all // other vertices as INFINITE for (int i = 0; i < V; ++i) dist[i] = int.MaxValue; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The // above step guarantees shortest distances if graph // doesn't contain negative weight cycle. If we get // a shorter path, then there is a cycle. for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) { Console.WriteLine( 'Graph contains negative weight cycle'); return; } } printArr(dist, V); } // A utility function used to print the solution void printArr(int[] dist, int V) { Console.WriteLine('Vertex Distance from Source'); for (int i = 0; i < V; ++i) Console.WriteLine(i + ' ' + dist[i]); } // Driver's code public static void Main() { int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; // Function call graph.BellmanFord(graph, 0); } // This code is contributed by Ryuga }> Javascript // a structure to represent a connected, directed and // weighted graph class Edge { constructor(src, dest, weight) { this.src = src; this.dest = dest; this.weight = weight; } } class Graph { constructor(V, E) { this.V = V; this.E = E; this.edge = []; } } function createGraph(V, E) { const graph = new Graph(V, E); for (let i = 0; i < E; i++) { graph.edge[i] = new Edge(); } return graph; } function printArr(dist, V) { console.log('Vertex Distance from Source'); for (let i = 0; i < V; i++) { console.log(`${i} ${dist[i]}`); } } function BellmanFord(graph, src) { const V = graph.V; const E = graph.E; const dist = []; for (let i = 0; i < V; i++) { dist[i] = Number.MAX_SAFE_INTEGER; } dist[src] = 0; for (let i = 1; i <= V - 1; i++) { for (let j = 0; j < E; j++) { const u = graph.edge[j].src; const v = graph.edge[j].dest; const weight = graph.edge[j].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } for (let i = 0; i < E; i++) { const u = graph.edge[i].src; const v = graph.edge[i].dest; const weight = graph.edge[i].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { console.log('Graph contains negative weight cycle'); return; } } printArr(dist, V); } // Driver program to test methods of graph class // Create a graph given in the above diagram const V = 5; const E = 8; const graph = createGraph(V, E); graph.edge[0] = new Edge(0, 1, -1); graph.edge[1] = new Edge(0, 2, 4); graph.edge[2] = new Edge(1, 2, 3); graph.edge[3] = new Edge(1, 3, 2); graph.edge[4] = new Edge(1, 4, 2); graph.edge[5] = new Edge(3, 2, 5); graph.edge[6] = new Edge(3, 1, 1); graph.edge[7] = new Edge(4, 3, -3); BellmanFord(graph, 0);> Ieșire
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>
Analiza complexității algoritmului Bellman-Ford :
- Complexitatea timpului când graficul este conectat:
- Cel mai bun caz: O(E), când matricea distanțelor după prima și a doua relaxare sunt aceleași, putem pur și simplu opri prelucrarea ulterioară
- Caz mediu: O(V*E)
- Cel mai rău caz: O(V*E)
- Timp Complexitatea când graficul este deconectat :
- Toate cazurile: O(E*(V^2))
- Spațiu auxiliar: O(V), unde V este numărul de vârfuri din grafic.
Aplicații ale algoritmului Bellman Ford:
- Rutare în rețea: Bellman-Ford este folosit în rețelele de calculatoare pentru a găsi cele mai scurte căi în tabelele de rutare, ajutând pachetele de date să navigheze eficient în rețele.
- Navigație GPS: dispozitivele GPS folosesc Bellman-Ford pentru a calcula cele mai scurte sau mai rapide rute între locații, ajutând aplicațiile și dispozitivele de navigare.
- Transport si logistica: Algoritmul Bellman-Ford poate fi aplicat pentru a determina căile optime pentru vehicule în transport și logistică, minimizând consumul de combustibil și timpul de călătorie.
- Dezvoltarea jocului: Bellman-Ford poate fi folosit pentru a modela mișcarea și navigarea în lumi virtuale în dezvoltarea jocurilor, unde diferite căi pot avea costuri sau obstacole diferite.
- Robotică și vehicule autonome: Algoritmul ajută la planificarea traseului pentru roboți sau vehicule autonome, luând în considerare obstacolele, terenul și consumul de energie.
Dezavantajul algoritmului lui Bellman Ford:
- Algoritmul Bellman-Ford va eșua dacă graficul conține orice ciclu de margine negativă.
Articole similare despre algoritmii cu cea mai scurtă cale cu o singură sursă: