10.9 Computing Multi-Source Shortest Paths

Most shortest-path problems begin with a single source vertex.

algorithmsshortest-pathsgraphs

10.9 Computing Multi-Source Shortest Paths

Most shortest-path problems begin with a single source vertex. We start at one location and ask for the shortest distance to every other location.

Some problems are naturally different.

A city may contain multiple hospitals, and we want the nearest hospital for every neighborhood. A game map may contain multiple spawn points, and we want the closest one for each position. A logistics network may contain several warehouses, and we want delivery distances from the nearest warehouse rather than from a particular warehouse.

These problems involve multiple starting points.

A naive solution runs a shortest-path algorithm once for each source and keeps the minimum distance. While correct, this approach often performs unnecessary work.

A more efficient technique treats all source vertices as active simultaneously.

This recipe shows how to solve multi-source shortest-path problems using a simple modification of existing algorithms.

Problem

Given a graph and a set of source vertices:

S = {s₁, s₂, ..., sₖ}

compute the distance from every vertex to its nearest source.

Consider:

Hospital A

0 --- 1 --- 2 --- 3

Hospital B

If hospitals are located at vertices:

0 and 3

the desired distances are:

0 -> 0
1 -> 1
2 -> 1
3 -> 0

Each vertex should be assigned the distance to its closest hospital.

Solution for Unweighted Graphs

The simplest solution is to initialize BFS with all source vertices.

Instead of inserting one starting vertex:

queue = append(queue, source)

insert every source.

for _, source := range sources {
	queue = append(queue, source)
	dist[source] = 0
}

The remainder of BFS remains unchanged.

package main

import "fmt"

func multiSourceBFS(graph [][]int, sources []int) []int {
	n := len(graph)

	dist := make([]int, n)

	for i := range dist {
		dist[i] = -1
	}

	queue := make([]int, 0)

	for _, source := range sources {
		dist[source] = 0
		queue = append(queue, source)
	}

	head := 0

	for head < len(queue) {
		v := queue[head]
		head++

		for _, next := range graph[v] {
			if dist[next] != -1 {
				continue
			}

			dist[next] = dist[v] + 1
			queue = append(queue, next)
		}
	}

	return dist
}

func main() {
	graph := [][]int{
		{1},
		{0, 2},
		{1, 3},
		{2},
	}

	fmt.Println(multiSourceBFS(graph, []int{0, 3}))
}

Output:

[0 1 1 0]

The algorithm automatically computes the nearest source for every vertex.

Understanding Why It Works

Imagine running BFS simultaneously from every source.

Initially:

0       3

Both vertices enter the queue.

distance = 0

The first expansion discovers:

1 and 2

with distance:

1

The search frontiers expand toward each other.

Eventually they meet.

The first frontier that reaches a vertex determines its shortest distance.

This is identical to ordinary BFS except that the initial frontier contains multiple vertices.

The Virtual Super Source

Another way to view the algorithm is through a graph transformation.

Create a new vertex:

S

and connect it to every source with zero-cost edges.

      S
    / | \\n   /  |  \\n  A   B   C

Running a shortest-path algorithm from:

S

produces the same distances as a multi-source search.

The virtual source perspective is useful because it generalizes to weighted graphs.

Multi-Source Dijkstra

For weighted graphs, initialize Dijkstra's priority queue with every source.

for _, source := range sources {
	dist[source] = 0

	heap.Push(pq, Item{
		Vertex:   source,
		Distance: 0,
	})
}

Everything else remains unchanged.

func multiSourceDijkstra(
	graph [][]Edge,
	sources []int,
) []int {

	const INF = int(1e18)

	dist := make([]int, len(graph))

	for i := range dist {
		dist[i] = INF
	}

	pq := &PriorityQueue{}
	heap.Init(pq)

	for _, source := range sources {
		dist[source] = 0

		heap.Push(pq, Item{
			Vertex:   source,
			Distance: 0,
		})
	}

	for pq.Len() > 0 {
		current := heap.Pop(pq).(Item)

		if current.Distance != dist[current.Vertex] {
			continue
		}

		for _, edge := range graph[current.Vertex] {
			candidate := current.Distance + edge.Weight

			if candidate >= dist[edge.To] {
				continue
			}

			dist[edge.To] = candidate

			heap.Push(pq, Item{
				Vertex:   edge.To,
				Distance: candidate,
			})
		}
	}

	return dist
}

Conceptually, Dijkstra now expands shortest paths outward from all sources simultaneously.

Finding the Closest Source

Distances alone are often insufficient.

Suppose we want:

Which hospital serves each neighborhood?

Store an owner array.

owner := make([]int, n)

Initialize:

for _, source := range sources {
	owner[source] = source
}

Whenever a vertex is discovered:

owner[next] = owner[current]

The source identity propagates together with the distance.

At completion:

Vertex Distance Closest Source
0 0 0
1 1 0
2 1 3
3 0 3

This technique appears frequently in facility-location systems and territory assignment problems.

Voronoi Regions on Graphs

Multi-source shortest paths naturally partition a graph.

Suppose sources exist at:

A
D
G

Every vertex belongs to whichever source is closest.

The graph becomes divided into regions.

AAAABBBCC
AAAABBBCC
AAAABBBCC

This is the graph equivalent of a Voronoi diagram.

Applications include:

  • Cellular tower coverage
  • Delivery routing
  • Resource assignment
  • Game AI territories
  • Emergency response planning

The implementation differs only by maintaining source ownership.

Discussion

Multi-source shortest paths are conceptually simpler than they first appear.

The key observation is:

Multiple sources can be treated as a single source frontier.

Every shortest-path algorithm begins with a set of vertices whose distances are already known.

Ordinarily that set contains one vertex.

Multi-source algorithms simply start with more.

This preserves all correctness arguments.

BFS remains BFS.

Dijkstra remains Dijkstra.

Only initialization changes.

This pattern appears throughout graph algorithms.

Many seemingly new algorithms are actually familiar algorithms with different initialization rules.

Complexity

Let:

  • V = vertices
  • E = edges
  • K = number of sources

Initialization requires:

O(K)

The traversal cost remains unchanged.

Multi-Source BFS

Operation Complexity
Initialization O(K)
BFS traversal O(V + E)
Total O(V + E)

Multi-Source Dijkstra

Operation Complexity
Initialization O(K)
Dijkstra traversal O((V + E) log V)
Total O((V + E) log V)

Notice that the complexity is effectively identical to the single-source version.

Common Mistakes

Do not run BFS or Dijkstra separately from every source unless you genuinely need independent distance maps.

Do not forget to initialize every source distance to zero.

Do not enqueue sources multiple times.

Do not assume ties resolve uniquely. Two sources may be equidistant from a vertex.

Do not forget ownership tracking when source identity matters.

Practical Applications

Multi-source shortest paths appear in:

  • Nearest hospital systems
  • Warehouse assignment
  • Delivery routing
  • Cellular coverage analysis
  • Road maintenance planning
  • Emergency response systems
  • Territory generation in games
  • Social-network influence analysis

Many nearest-facility problems reduce directly to this pattern.

Takeaway

Multi-source shortest paths require no fundamentally new algorithm. Initialize all source vertices with distance zero and allow the search frontier to expand from every source simultaneously. This simple modification transforms BFS and Dijkstra into powerful nearest-facility algorithms while preserving their original complexity guarantees.