Shortest Path in Weighted Graph

Definition

A shortest path in a weighted graph is a path from one vertex to another vertex for which the sum of the weights of all edges in the path is minimum among all possible paths connecting those two vertices.

If a graph is represented as $G = (V, E)$, where:

• $V$ is the set of vertices,
• $E$ is the set of weighted edges,

and each edge $e \in E$ has a weight $w(e)$, then the shortest path between two vertices $u$ and $v$ is the path $P$ such that:

$$\text{Cost}(P) = \sum w(e)$$

is the least possible among all paths from $u$ to $v$.

A graph may contain:

Positive weights

Zero weights

Negative weights

• in some cases

However, the choice of algorithm depends on the type of weights present. For example, Dijkstra’s algorithm works only when all edge weights are non-negative, while Bellman-Ford algorithm can handle negative weights.

Main Content

1. Weighted Graph and Path Cost

• In a weighted graph, every edge has a numerical value attached to it. This value may represent:
• distance between cities,
• cost of travel,
• time taken to move,
• or any measurable quantity relevant to the problem.
• The cost of a path is the sum of all the edge weights along that path. The shortest path is not necessarily the one with the fewest edges; it is the one with the minimum total cost.

Example:

Suppose there are two paths from A to D:

• Path 1: A → B → D
  Weights: 4 + 6 = 10

• Path 2: A → C → D
  Weights: 2 + 9 = 11

Even if both paths use two edges, Path 1 is shorter because its total weight is smaller.

Graph illustration:

A --4-- B --6-- D
 \      |
  2     1
   \    |
     C --9--

If the path A → C → D has weights 2 and 9, its total cost is 11.
If A → B → D has weights 4 and 6, its total cost is 10.
So, A → B → D is the shortest path from A to D.

2. Shortest Path Problems and Their Types

• The shortest path problem can be classified into different types depending on the source and destination:
• Single-source shortest path: Find the shortest path from one source vertex to all other vertices.
• Single-pair shortest path: Find the shortest path between one specific source and one specific destination.
• All-pairs shortest path: Find the shortest path between every pair of vertices.
• Different algorithms are used for different types of problems:
• Dijkstra’s algorithm for single-source shortest path with non-negative weights.
• Bellman-Ford algorithm for graphs that may contain negative weights.
• Floyd-Warshall algorithm for all-pairs shortest path.

Example:

In a road network:

• A single driver wants the quickest route from home to office → single-pair shortest path
• A navigation app wants distances from one city to all nearby cities → single-source shortest path
• A transportation planner wants minimum distances between every pair of cities → all-pairs shortest path

This classification helps in choosing the right algorithm based on the need and size of the graph.

3. Algorithms Used to Find the Shortest Path

Dijkstra’s Algorithm

• Used when all edge weights are non-negative.
• It repeatedly chooses the vertex with the smallest temporary distance.
• It is efficient and widely used in practice.
• It does not work correctly if negative edge weights exist.

Bellman-Ford Algorithm

• Works even if some edges have negative weights.
• It relaxes edges repeatedly for $V-1$ times.
• It can also detect negative weight cycles.
• It is slower than Dijkstra’s algorithm but more general.

Floyd-Warshall Algorithm

• Finds shortest paths between all pairs of vertices.
• Uses dynamic programming.
• Suitable for dense graphs and smaller graphs.
• Also handles negative edge weights, but not negative cycles.

Simple comparison idea:

• If the graph has only non-negative weights and you need one source → use Dijkstra
• If negative edges exist → use Bellman-Ford
• If you need shortest paths for every pair → use Floyd-Warshall

Working / Process

1. Represent the graph clearly

• Store the graph using an adjacency matrix or adjacency list.
• Note the weight of every edge carefully.
• Identify whether the graph is directed or undirected, because this affects the paths.

2. Choose the appropriate algorithm

• If all weights are non-negative, select Dijkstra’s algorithm.
• If negative weights are present, use Bellman-Ford.
• If shortest paths are required between all pairs of vertices, use Floyd-Warshall.

3. Compute the minimum distances step by step

• Start from the source vertex and assign distance 0 to it and infinity to others.
• Update distances by comparing current values with newly found path costs.
• Continue until no shorter distances can be found.
• Finally, trace back the predecessor or parent array to reconstruct the actual shortest path.

Example using Dijkstra’s method:

Consider vertices A, B, C, D with edges:

• A → B = 1
• A → C = 4
• B → C = 2
• B → D = 5
• C → D = 1

Starting from A:

• Distance to A = 0
• Distance to B = 1
• Distance to C = 4, then improved to 3 through B
• Distance to D = 4 through C

Shortest path from A to D:

• A → B → C → D
• Total weight = 1 + 2 + 1 = 4

This process shows how shorter intermediate routes can improve the final answer.

Advantages / Applications

• Helps find the minimum-cost route in transportation and navigation systems such as Google Maps and GPS.
• Used in computer networks to find efficient routing paths for data packets.
• Applied in logistics and supply chain management to reduce fuel, time, and delivery cost.
• Important in network design, robotics, games, and AI pathfinding, where selecting an optimal route is essential.

Summary

• The shortest path in a weighted graph is the path with the minimum total edge weight.
• The answer depends on edge weights, not just the number of edges.
• Different algorithms are used depending on whether weights are non-negative, negative, or whether all-pairs paths are needed.
• Shortest path techniques are widely used in real-world systems like maps, networking, and optimization.