Session 6
Single Source Shortest Path Algorithm
This session introduces shortest path problems in weighted graphs. The main idea is to start from one source vertex and compute the minimum distance to every other vertex. This is useful in routing, maps, network design, and any problem where we need the cheapest or shortest route from one point to many destinations.
Objectives
- Understand single-source shortest path problems.
- Apply Dijkstra's algorithm when all edge weights are non-negative.
- Identify why negative edge weights require a different algorithm such as Bellman-Ford.
Concept
A single-source shortest path algorithm finds the minimum distance from one starting vertex to every other vertex in a weighted graph.
| Algorithm | Suitable When |
|---|---|
| Dijkstra | All edge weights are zero or positive |
| Bellman-Ford | Negative edge weights may exist |
Standard Dijkstra Approach
- Set the source distance to
0and all other distances to infinity. - Pick the unvisited vertex with the smallest known distance.
- Relax all outgoing edges from that vertex.
- Repeat until all vertices are processed.
Standard Bellman-Ford Approach
- Set the source distance to
0and all other distances to infinity. - Relax every edge
V - 1times. - Run one more relaxation pass to detect a negative cycle.
Common statement
It's for all three questions in this sessions.
Implement Dijkstra’s algorithm to find the single source shortest path algorithm from different sources to the rest of nodes in the following graph and show allthe intermediate processes:
Dijkstra's Algorithm Implementation
This code also includes solutions for all the three question as code and text part is explained standalone. This is done because of implementation requirement for code.
Python
"""
Dijkstra's Algorithm Implementation
Finds shortest path from source to all other vertices
"""
import heapq
from collections import defaultdict
class DijkstraAlgorithm:
def __init__(self):
# Graph represented as adjacency list
self.graph = defaultdict(list)
def add_edge(self, u, v, weight):
"""Add directed edge from u to v with given weight"""
self.graph[u].append((v, weight))
def dijkstra(self, source, vertices):
"""Dijkstra's algorithm to find shortest paths from source
Args:
source: Starting vertex
vertices: List of all vertices
Returns:
distances: Shortest distance from source to each vertex
previous: Previous vertex in shortest path
steps: Intermediate steps for visualization
"""
# Initialize distances to infinity
distances = {v: float("inf") for v in vertices}
distances[source] = 0
# Track previous vertex for path reconstruction
previous = {v: None for v in vertices}
# Track visited vertices
visited = set()
# Priority queue: (distance, vertex)
pq = [(0, source)]
# Store intermediate steps
steps = []
iteration = 0
while pq:
iteration += 1
current_dist, current_vertex = heapq.heappop(pq)
# Skip if already visited
if current_vertex in visited:
continue
# Mark as visited
visited.add(current_vertex)
# Record this step
step = {
"iteration": iteration,
"current_vertex": current_vertex,
"current_distance": current_dist,
"distances": distances.copy(),
"visited": visited.copy(),
}
steps.append(step)
# Explore neighbors
for neighbor, weight in self.graph[current_vertex]:
if neighbor not in visited:
new_distance = current_dist + weight
# If shorter path found
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
previous[neighbor] = current_vertex
heapq.heappush(pq, (new_distance, neighbor))
return distances, previous, steps
def get_path(self, previous, source, target):
"""Reconstruct path from source to target"""
path = []
current = target
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path if path[0] == source else []
def print_dijkstra_steps(steps, distances, previous, source, vertices):
"""Print detailed step-by-step execution"""
print("\n" + "=" * 80)
print(f"DIJKSTRA'S ALGORITHM - Source: {source}")
print("=" * 80)
for step in steps:
print(f"\nIteration {step['iteration']}:")
print(f" Current Vertex: {step['current_vertex']}")
print(f" Distance to {step['current_vertex']}: {step['current_distance']}")
print(f" Visited: {sorted(step['visited'])}")
print(" Current Distances: ", end="")
for v in sorted(vertices):
dist = step["distances"][v]
if dist == float("inf"):
print(f"{v}=∞ ", end="")
else:
print(f"{v}={dist} ", end="")
print()
print("\n" + "=" * 80)
print("FINAL RESULTS:")
print("=" * 80)
for v in sorted(vertices):
dist = distances[v]
if dist == float("inf"):
print(f"Distance from {source} to {v}: ∞ (unreachable)")
else:
path = []
current = v
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
path_str = " → ".join(path)
print(f"Distance from {source} to {v}: {dist} | Path: {path_str}")
if __name__ == "__main__":
# Create graph instance
dijkstra = DijkstraAlgorithm()
# Define all vertices
vertices = ["A", "B", "C", "D", "E", "F", "G"]
# Add edges (original graph)
dijkstra.add_edge("A", "B", 6)
dijkstra.add_edge("A", "G", 4)
dijkstra.add_edge("B", "C", 2)
dijkstra.add_edge("B", "D", 4)
dijkstra.add_edge("C", "D", 2)
dijkstra.add_edge("G", "D", 8)
dijkstra.add_edge("G", "F", 8)
dijkstra.add_edge("D", "F", 2)
dijkstra.add_edge("D", "E", 1)
dijkstra.add_edge("F", "A", 3)
dijkstra.add_edge("F", "E", 7)
# =========================================================================
# Q1: Shortest path from A to rest of vertices
# =========================================================================
print("\n" + "#" * 80)
print("# Q1: SHORTEST PATH FROM A TO ALL VERTICES")
print("#" * 80)
distances_A, previous_A, steps_A = dijkstra.dijkstra("A", vertices)
print_dijkstra_steps(steps_A, distances_A, previous_A, "A", vertices)
# =========================================================================
# Q2: Shortest path from B to rest of vertices
# =========================================================================
print("\n\n" + "#" * 80)
print("# Q2: SHORTEST PATH FROM B TO ALL VERTICES")
print("#" * 80)
# Create new graph for source B
dijkstra_B = DijkstraAlgorithm()
dijkstra_B.add_edge("A", "B", 6)
dijkstra_B.add_edge("A", "G", 4)
dijkstra_B.add_edge("B", "C", 2)
dijkstra_B.add_edge("B", "D", 4)
dijkstra_B.add_edge("C", "D", 2)
dijkstra_B.add_edge("G", "D", 8)
dijkstra_B.add_edge("G", "F", 8)
dijkstra_B.add_edge("D", "F", 2)
dijkstra_B.add_edge("D", "E", 1)
dijkstra_B.add_edge("F", "A", 3)
dijkstra_B.add_edge("F", "E", 7)
distances_B, previous_B, steps_B = dijkstra_B.dijkstra("B", vertices)
print_dijkstra_steps(steps_B, distances_B, previous_B, "B", vertices)
# =========================================================================
# Q3: Graph with negative weights (G→F = -8, F→A = -3)
# =========================================================================
print("\n\n" + "#" * 80)
print("# Q3: SHORTEST PATH FROM A WITH NEGATIVE WEIGHTS")
print("# Note: Dijkstra's algorithm DOES NOT WORK with negative weights!")
print("# We'll show why it fails and use Bellman-Ford instead")
print("#" * 80)
# Show Dijkstra failure
dijkstra_neg = DijkstraAlgorithm()
dijkstra_neg.add_edge("A", "B", 6)
dijkstra_neg.add_edge("A", "G", 4)
dijkstra_neg.add_edge("B", "C", 2)
dijkstra_neg.add_edge("B", "D", 4)
dijkstra_neg.add_edge("C", "D", 2)
dijkstra_neg.add_edge("G", "D", 8)
dijkstra_neg.add_edge("G", "F", -8) # NEGATIVE WEIGHT
dijkstra_neg.add_edge("D", "F", 2)
dijkstra_neg.add_edge("D", "E", 1)
dijkstra_neg.add_edge("F", "A", -3) # NEGATIVE WEIGHT
dijkstra_neg.add_edge("F", "E", 7)
print("\n⚠️ PROBLEM: Dijkstra's algorithm fails with negative weights!")
print(" Reason: Once a vertex is marked 'visited', Dijkstra assumes")
print(" the shortest path is found. But negative edges can create")
print(" shorter paths later, which Dijkstra will miss.")
# Implement Bellman-Ford for negative weights
def bellman_ford(graph, source, vertices):
"""Bellman-Ford algorithm that handles negative weights"""
distances = {v: float("inf") for v in vertices}
distances[source] = 0
previous = {v: None for v in vertices}
# Relax all edges |V| - 1 times
for i in range(len(vertices) - 1):
updated = False
for u in vertices:
# Only check paths if u itself is reachable
if u in graph and distances[u] != float("inf"):
for v, weight in graph[u]:
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
previous[v] = u
updated = True
if not updated:
break
# Check for negative weight cycles
for u in vertices:
if u in graph and distances[u] != float("inf"):
for v, weight in graph[u]:
if distances[u] + weight < distances[v]:
print(
"\n⚠️ CRITICAL ERROR: Graph contains a negative weight cycle!"
)
print(
" Shortest paths cannot be accurately found because you can loop infinitely to decrease distance."
)
return None, None
return distances, previous
# Build graph for Bellman-Ford
graph_neg = defaultdict(list)
graph_neg["A"] = [("B", 6), ("G", 4)]
graph_neg["B"] = [("C", 2), ("D", 4)]
graph_neg["C"] = [("D", 2)]
graph_neg["G"] = [("D", 8), ("F", -8)]
graph_neg["D"] = [("F", 2), ("E", 1)]
graph_neg["F"] = [("A", -3), ("E", 7)]
distances_neg, previous_neg = bellman_ford(graph_neg, "A", vertices)
print("\n" + "=" * 80)
print("BELLMAN-FORD ALGORITHM (Handles Negative Weights)")
print("=" * 80)
if distances_neg is None:
print("Could not calculate final paths due to the negative weight cycle.")
else:
for v in sorted(vertices):
dist = distances_neg[v]
if dist == float("inf"):
print(f"Distance from A to {v}: ∞ (unreachable)")
else:
path = []
current = v
visited_in_path = set()
while current is not None and current not in visited_in_path:
path.append(current)
visited_in_path.add(current)
current = previous_neg[current]
if len(path) > len(vertices): # Safety check
break
path.reverse()
if path and path[0] == "A":
path_str = " → ".join(path)
print(f"Distance from A to {v}: {dist} | Path: {path_str}")
else:
print(f"Distance from A to {v}: {dist} | Path: (cycle detected)")
C Language
/*
* Dijkstra's Algorithm Implementation in C
* Finds shortest path from source to all vertices
*
* Compilation: gcc -o dijkstra dijkstra.c -std=c99
* Execution: ./dijkstra
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#define MAX_VERTICES 7
#define INF INT_MAX
// Structure to represent the graph
typedef struct {
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
char vertices[MAX_VERTICES];
int numVertices;
} Graph;
// Structure to store distance information
typedef struct {
int distance;
int previous;
bool visited;
} DistInfo;
// Initialize graph
void initGraph(Graph *g) {
g->numVertices = MAX_VERTICES;
g->vertices[0] = 'A';
g->vertices[1] = 'B';
g->vertices[2] = 'C';
g->vertices[3] = 'D';
g->vertices[4] = 'E';
g->vertices[5] = 'F';
g->vertices[6] = 'G';
// Initialize adjacency matrix with INF
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
g->adjMatrix[i][j] = INF;
}
}
}
// Add edge to graph
void addEdge(Graph *g, char from, char to, int weight) {
int fromIdx = -1, toIdx = -1;
// Find indices
for (int i = 0; i < g->numVertices; i++) {
if (g->vertices[i] == from) fromIdx = i;
if (g->vertices[i] == to) toIdx = i;
}
if (fromIdx != -1 && toIdx != -1) {
g->adjMatrix[fromIdx][toIdx] = weight;
}
}
// Find vertex with minimum distance
int findMinDistance(DistInfo dist[], int numVertices) {
int min = INF;
int minIndex = -1;
for (int i = 0; i < numVertices; i++) {
if (!dist[i].visited && dist[i].distance < min) {
min = dist[i].distance;
minIndex = i;
}
}
return minIndex;
}
// Print path
void printPath(Graph *g, int previous[], int target) {
if (previous[target] == -1) {
printf("%c", g->vertices[target]);
return;
}
printPath(g, previous, previous[target]);
printf(" -> %c", g->vertices[target]);
}
// Dijkstra's algorithm
void dijkstra(Graph *g, char source) {
DistInfo dist[MAX_VERTICES];
int previous[MAX_VERTICES];
int sourceIdx = -1;
// Find source index
for (int i = 0; i < g->numVertices; i++) {
if (g->vertices[i] == source) {
sourceIdx = i;
break;
}
}
// Initialize distances
for (int i = 0; i < g->numVertices; i++) {
dist[i].distance = INF;
dist[i].visited = false;
previous[i] = -1;
}
dist[sourceIdx].distance = 0;
printf("\n%s\n", "==========================================================");
printf("DIJKSTRA'S ALGORITHM - Source: %c\n", source);
printf("%s\n", "==========================================================");
// Main loop
for (int count = 0; count < g->numVertices - 1; count++) {
int u = findMinDistance(dist, g->numVertices);
if (u == -1 || dist[u].distance == INF) break;
dist[u].visited = true;
printf("\nIteration %d: Processing vertex %c (distance: %d)\n",
count + 1, g->vertices[u], dist[u].distance);
// Update distances of adjacent vertices
for (int v = 0; v < g->numVertices; v++) {
if (g->adjMatrix[u][v] != INF && !dist[v].visited) {
int newDist = dist[u].distance + g->adjMatrix[u][v];
if (newDist < dist[v].distance) {
dist[v].distance = newDist;
previous[v] = u;
printf(" Updated %c: distance = %d\n",
g->vertices[v], newDist);
}
}
}
}
// Print final results
printf("\n%s\n", "==========================================================");
printf("FINAL RESULTS:\n");
printf("%s\n", "==========================================================");
for (int i = 0; i < g->numVertices; i++) {
printf("Distance from %c to %c: ", source, g->vertices[i]);
if (dist[i].distance == INF) {
printf("∞ (unreachable)\n");
} else {
printf("%d | Path: %c -> ", dist[i].distance, source);
printPath(g, previous, i);
printf("\n");
}
}
}
int main() {
Graph g;
initGraph(&g);
// Add edges (original graph)
addEdge(&g, 'A', 'B', 6);
addEdge(&g, 'A', 'G', 4);
addEdge(&g, 'B', 'C', 2);
addEdge(&g, 'B', 'D', 4);
addEdge(&g, 'C', 'D', 2);
addEdge(&g, 'G', 'D', 8);
addEdge(&g, 'G', 'F', 8);
addEdge(&g, 'D', 'F', 2);
addEdge(&g, 'D', 'E', 1);
addEdge(&g, 'F', 'A', 3);
addEdge(&g, 'F', 'E', 7);
// Q1: Shortest path from A
printf("\n%s\n", "##################################################");
printf("# Q1: SHORTEST PATH FROM A TO ALL VERTICES");
printf("%s\n", "##################################################");
dijkstra(&g, 'A');
// Q2: Shortest path from B
printf("\n\n%s\n", "##################################################");
printf("# Q2: SHORTEST PATH FROM B TO ALL VERTICES");
printf("%s\n", "##################################################");
dijkstra(&g, 'B');
return 0;
}
Rust
/*
* Dijkstra's Algorithm Implementation in Rust
* Finds shortest path from source to all vertices
*
* Compilation: rustc -o dijkstra dijkstra.rs
* Execution: ./dijkstra
*/
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap, HashSet};
// Structure to represent an edge
#[derive(Debug, Clone)]
struct Edge {
to: char,
weight: i32,
}
// Structure for priority queue
#[derive(Debug, Eq, PartialEq)]
struct QueueItem {
distance: i32,
vertex: char,
}
// Implement ordering for min-heap
impl Ord for QueueItem {
fn cmp(&self, other: &Self) -> Ordering {
other
.distance
.cmp(&self.distance)
.then_with(|| self.vertex.cmp(&other.vertex))
}
}
impl PartialOrd for QueueItem {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
// Graph structure
struct Graph {
adjacency_list: HashMap<char, Vec<Edge>>,
vertices: Vec<char>,
}
impl Graph {
fn new() -> Self {
Graph {
adjacency_list: HashMap::new(),
vertices: vec!['A', 'B', 'C', 'D', 'E', 'F', 'G'],
}
}
fn add_edge(&mut self, from: char, to: char, weight: i32) {
self.adjacency_list
.entry(from)
.or_insert_with(Vec::new)
.push(Edge { to, weight });
}
fn dijkstra(&self, source: char) -> (HashMap<char, i32>, HashMap<char, Option<char>>) {
let mut distances: HashMap<char, i32> =
self.vertices.iter().map(|&v| (v, i32::MAX)).collect();
let mut previous: HashMap<char, Option<char>> =
self.vertices.iter().map(|&v| (v, None)).collect();
let mut visited: HashSet<char> = HashSet::new();
let mut heap = BinaryHeap::new();
*distances.get_mut(&source).unwrap() = 0;
heap.push(QueueItem {
distance: 0,
vertex: source,
});
println!("\n{}", "=".repeat(70));
println!("DIJKSTRA'S ALGORITHM - Source: {}", source);
println!("{}", "=".repeat(70));
let mut iteration = 0;
while let Some(QueueItem {
distance: current_dist,
vertex: current_vertex,
}) = heap.pop()
{
if visited.contains(¤t_vertex) {
continue;
}
visited.insert(current_vertex);
iteration += 1;
println!(
"\nIteration {}: Processing vertex {} (distance: {})",
iteration, current_vertex, current_dist
);
if let Some(edges) = self.adjacency_list.get(¤t_vertex) {
for edge in edges {
if !visited.contains(&edge.to) {
let new_distance = current_dist + edge.weight;
if new_distance < *distances.get(&edge.to).unwrap() {
*distances.get_mut(&edge.to).unwrap() = new_distance;
*previous.get_mut(&edge.to).unwrap() = Some(current_vertex);
heap.push(QueueItem {
distance: new_distance,
vertex: edge.to,
});
println!(" Updated {}: distance = {}", edge.to, new_distance);
}
}
}
}
}
// Print results
println!("\n{}", "=".repeat(70));
println!("FINAL RESULTS:");
println!("{}", "=".repeat(70));
for &vertex in &self.vertices {
print!("Distance from {} to {}: ", source, vertex);
let dist = *distances.get(&vertex).unwrap();
if dist == i32::MAX {
println!("∞ (unreachable)");
} else {
println!("{}", dist);
}
}
(distances, previous)
}
}
fn main() {
let mut graph = Graph::new();
// Add edges
graph.add_edge('A', 'B', 6);
graph.add_edge('A', 'G', 4);
graph.add_edge('B', 'C', 2);
graph.add_edge('B', 'D', 4);
graph.add_edge('C', 'D', 2);
graph.add_edge('G', 'D', 8);
graph.add_edge('G', 'F', 8);
graph.add_edge('D', 'F', 2);
graph.add_edge('D', 'E', 1);
graph.add_edge('F', 'A', 3);
graph.add_edge('F', 'E', 7);
// Q1: From A
println!("\n{}", "#".repeat(70));
println!("# Q1: SHORTEST PATH FROM A TO ALL VERTICES");
println!("{}", "#".repeat(70));
graph.dijkstra('A');
// Q2: From B
println!("\n\n{}", "#".repeat(70));
println!("# Q2: SHORTEST PATH FROM B TO ALL VERTICES");
println!("{}", "#".repeat(70));
graph.dijkstra('B');
}
Question 1
Problem Statement
Find the shortest path from A to the rest of vertices.
Explanation / Approach
Use Dijkstra's algorithm if all edge weights in the graph are non-negative. Start with distance of A = 0, mark all other vertices as infinity, and repeatedly relax the nearest unvisited vertex.
Answer
Initial State
Distances: A=0, B=∞, C=∞, D=∞, E=∞, F=∞, G=∞
Visited: {}
Iteration 1: Process A (dist=0)
Neighbors: B(6), G(4)
Update: B=0+6=6, G=0+4=4
Distances: A=0, B=6, C=∞, D=∞, E=∞, F=∞, G=4
Visited: {A}
Iteration 2: Process G (dist=4) ← Minimum unvisited
Neighbors: D(8), F(8)
Update: D=4+8=12, F=4+8=12
Distances: A=0, B=6, C=∞, D=12, E=∞, F=12, G=4
Visited: {A, G}
Iteration 3: Process B (dist=6) ← Minimum unvisited
Neighbors: C(2), D(4)
Update: C=6+2=8, D=min(12, 6+4)=10
Distances: A=0, B=6, C=8, D=10, E=∞, F=12, G=4
Visited: {A, G, B}
Iteration 4: Process C (dist=8) ← Minimum unvisited
Neighbors: D(2)
Update: D=min(10, 8+2)=10 (no change)
Distances: A=0, B=6, C=8, D=10, E=∞, F=12, G=4
Visited: {A, G, B, C}
Iteration 5: Process D (dist=10) ← Minimum unvisited
Neighbors: F(2), E(1)
Update: F=min(12, 10+2)=12 (no change), E=10+1=11
Distances: A=0, B=6, C=8, D=10, E=11, F=12, G=4
Visited: {A, G, B, C, D}
Iteration 6: Process E (dist=11) ← Minimum unvisited
Neighbors: (none that improve distances)
Distances: A=0, B=6, C=8, D=10, E=11, F=12, G=4
Visited: {A, G, B, C, D, E}
Iteration 7: Process F (dist=12) ← Last unvisited
Neighbors: A(3), E(7)
Both already visited, no updates
Final: A=0, B=6, C=8, D=10, E=11, F=12, G=4
Final Answer
A→A: 0 (Path: A)
A→B: 6 (Path: A→B)
A→C: 8 (Path: A→B→C)
A→D: 10 (Path: A→B→D)
A→E: 11 (Path: A→B→D→E)
A→F: 12 (Path: A→G→F or A→B→D→F)
A→G: 4 (Path: A→G)
Question 2
Problem Statement
Find the shortest path from B to the rest of nodes.
Explanation / Approach
The method is the same as Question 1, but the source vertex changes to B. The initial distance table should therefore start with B = 0 and all other vertices as infinity.
Answer
Initial State:
Distances: A=∞, B=0, C=∞, D=∞, E=∞, F=∞, G=∞
Iteration 1: Process B (dist=0)
Update: C=2, D=4
Distances: A=∞, B=0, C=2, D=4, E=∞, F=∞, G=∞
Iteration 2: Process C (dist=2)
Update: D=min(4, 2+2)=4
Distances: A=∞, B=0, C=2, D=4, E=∞, F=∞, G=∞
Iteration 3: Process D (dist=4)
Update: F=4+2=6, E=4+1=5
Distances: A=∞, B=0, C=2, D=4, E=5, F=6, G=∞
Iteration 4: Process E (dist=5)
No updates
Iteration 5: Process F (dist=6)
Update: A=6+3=9, E=min(5, 6+7)=5
Distances: A=9, B=0, C=2, D=4, E=5, F=6, G=∞
Iteration 6: Process A (dist=9)
Update: B=min(0, 9+6)=0, G=9+4=13
Distances: A=9, B=0, C=2, D=4, E=5, F=6, G=13
Iteration 7: Process G (dist=13)
Update: D=min(4, 13+8)=4, F=min(6, 13+8)=6
Final: A=9, B=0, C=2, D=4, E=5, F=6, G=13
Final Answer
B→A: 9 (Path: B→D→F→A)
B→B: 0 (Path: B)
B→C: 2 (Path: B→C)
B→D: 4 (Path: B→D)
B→E: 5 (Path: B→D→E)
B→F: 6 (Path: B→D→F)
B→G: 13 (Path: B→D→F→A→G)
Question 3
Problem Statement
Find the shortest path from A to the rest of vertices when there are negative weights -8 between G and F and -3 between F and A.
Explanation / Approach
Dijkstra's algorithm should not be used when negative edge weights exist. For this case, use Bellman-Ford reasoning because it can handle negative edges and can also detect negative cycles.
Answer
CRITICAL ISSUE: Dijkstra's algorithm FAILS with negative weights
Why it fails:
- Dijkstra marks vertices as "visited" permanently
- It assumes once visited, the shortest path is found
- Negative edges can create shorter paths through already-visited vertices
- This violates Dijkstra's greedy assumption
Example of failure:
With G→F=-8 and F→A=-3:
Path A→G→F→A creates a cycle: 4 + (-8) + (-3) = -7
This creates a NEGATIVE CYCLE!
You can loop infinitely to reduce distance.
Viva Questions
- Why does Dijkstra fail with negative edge weights?
- What is edge relaxation?
- How does Bellman-Ford detect a negative cycle?