Bellman-Ford & Floyd-Warshall (Introduction)
Bellman-Ford & Floyd-Warshall
Welcome! While Dijkstra's algorithm is efficient, it has its limits. What if a graph has negative edge weights? Or what if you need to find the shortest paths between all pairs of vertices? For these scenarios, we turn to two powerful algorithms: Bellman-Ford and Floyd-Warshall.
1. Bellman-Ford Algorithm
The Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices, just like Dijkstra. However, it has the crucial ability to handle graphs with negative edge weights.
1.1. The Core Idea: Relaxing All Edges
Instead of a greedy approach, Bellman-Ford uses a more methodical process. It repeatedly relaxes every single edge in the graph. A single pass of relaxing all edges will find all shortest paths of length 1. A second pass will find all shortest paths of length 2, and so on. Since the longest possible simple path in a graph with N vertices has N-1 edges, repeating this process N-1 times guarantees finding the shortest path.
1.2. The Algorithm Step-by-Step
-
Initialization:
- Create a
distancesarray. Set thesourcedistance to 0 and all others to infinity.
- Create a
-
Relaxation Loops:
- Repeat
N-1times:- For each edge
(u, v)with weightwin the graph:- If
distances[u] + w < distances[v], updatedistances[v] = distances[u] + w.
- If
- For each edge
- Repeat
-
Negative Cycle Detection:
- After
N-1iterations, perform one more (the Nth) iteration:- For each edge
(u, v)with weightw:- If
distances[u] + w < distances[v], it means a shorter path can still be found. This is only possible if a negative-weight cycle exists.
- If
- For each edge
- After
1.3. Implementation
function bellmanFord(N, edges, src) {
const dist = Array(N).fill(Infinity);
dist[src] = 0;
// Relax edges N-1 times
for (let i = 0; i < N - 1; i++) {
for (const { u, v, w } of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check for negative cycles
for (const { u, v, w } of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
throw new Error("Graph contains a negative-weight cycle");
}
}
return dist;
}
1.4. Complexity Analysis
- Time Complexity:
O(N * M), whereNis the number of vertices andMis the number of edges. - Space Complexity:
O(N)to store distances.
2. Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is designed for a different problem: finding the All-Pairs Shortest Paths (APSP). It calculates the shortest path between every single pair of vertices in the graph.
2.1. The Core Idea: Dynamic Programming
Floyd-Warshall uses a dynamic programming approach. It considers all possible vertices as "intermediate" nodes in a path. It iteratively builds up a solution by asking, "Can we find a shorter path from vertex i to vertex j by going through vertex k?"
2.2. The Algorithm Step-by-Step
-
Initialization:
- Create an
N x Nmatrixdistwheredist[i][j]is the weight of the edge fromitoj, or infinity if no direct edge exists.dist[i][i]should be 0.
- Create an
-
Main Loops:
- For each vertex
kfrom 0 toN-1(as the intermediate vertex):- For each vertex
ifrom 0 toN-1(as the start vertex):- For each vertex
jfrom 0 toN-1(as the end vertex):- Update
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
- Update
- For each vertex
- For each vertex
- For each vertex
-
Completion:
- After the loops complete, the
distmatrix will contain the shortest path distances between all pairs of vertices.
- After the loops complete, the
2.3. Implementation
function floydWarshall(N, initialDist) {
const dist = initialDist; // Make a copy if you need to preserve the original
for (let k = 0; k < N; k++) {
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
2.4. Complexity Analysis
- Time Complexity:
O(N^3), due to the three nested loops. - Space Complexity:
O(N^2)to store the distance matrix.
Key Takeaway:
- Use Bellman-Ford for single-source shortest paths when you have negative edge weights.
- Use Floyd-Warshall when you need to find the shortest paths between all pairs of vertices, especially in dense graphs where its
O(N^3)complexity is acceptable.
التالي · الدرس 66 من 92
Prim's Algorithm
قراءة 2 دقيقة
أنهيت 65 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

