Path-Relaxation Property

In shortest paths algorithms like Bellman-Ford, the path-relaxation property states that:

If there is a shortest path from u to v that contains edge (x,y), then dist[v] <= dist[x] + weight(x,y).

That is, the shortest path distance to v is bounded by the distance of the preceding vertex plus the edge weight.

This key property leads to an iterative relaxation algorithm:

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Bellman-Ford algorithm
void bellmanFord(Graph graph, int source) {
  dist[source] = 0;

  for (int i = 0; i < graph.vertices(); i++) {
    for (Edge edge : graph.edges()) {
      int u = edge.from();
      int v = edge.to();

      // Path relaxation  
      if (dist[u] != Integer.MAX_VALUE && dist[u] + edge.weight() < dist[v]) {
        dist[v] = dist[u] + edge.weight();
      }
    }
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Bellman-Ford algorithm
void bellmanFord(Graph graph, int source) {
  dist[source] = 0;

  for (int i = 0; i < graph.V; i++) {
    for (auto edge : graph.edges) {
      int u = edge.from;
      int v = edge.to;

      // Path relaxation
      if (dist[u] != INF && dist[u] + edge.cost < dist[v]) {
        dist[v] = dist[u] + edge.cost;  
      } 
    }
  }
}

Python example:

1
2
3
4
5
6
7
8
9

# Bellman-Ford algorithm
def bellman_ford(graph, source):

  dist[source] = 0
  
  for _ in range(graph.V-1):
    for u, v, w in graph.edges:
      if dist[u] != float("inf") and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

Path relaxation is the key optimal substructure enabling shortest path algorithms.

Path-relaxation property is crucial in understanding shortest-path algorithms like Dijkstra’s and Bellman-Ford. It involves “relaxing” the edges, i.e., updating the shortest-path estimate for vertices if a shorter path is found. A single relaxation step for an edge ( (u, v) ) tries to improve the shortest-path estimate from ( u ) to ( v ) using the path through ( u ).

Algorithm

  1. Initialization: We initialize the distance of all vertices to infinity except the source vertex, which is set to 0.
  2. Relaxation: For an edge ( (u, v) ) with weight ( w(u, v) ), if ( dist[u] + w(u, v) < dist[v] ), we update ( dist[v] ).

Java Code

1
2
3
4
5
6

public void relax(int u, int v, int[] dist, int[][] graph) {
    int weight = graph[u][v];
    if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
    }
}

C++ Code

1
2
3
4
5
6

void relax(int u, int v, std::vector<int>& dist, std::vector<std::vector<int>>& graph) {
    int weight = graph[u][v];
    if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
    }
}

Python Code

1
2
3
4

def relax(u, v, dist, graph):
    weight = graph[u][v]
    if dist[u] != float('inf') and dist[u] + weight < dist[v]:
        dist[v] = dist[u] + weight

In each of these code snippets, dist is an array storing the shortest-path estimates, graph is a 2D array representing the weighted graph, and ( (u, v) ) represents an edge from vertex ( u ) to ( v ). The function relax updates the shortest-path estimate for vertex ( v ) if a shorter path through ( u ) is found.