Shortest Path
Lesson 12 of 14 in Coddy's Graphs - Data Structures Series #9 course.
How few edges does it take to get from start to end? In an unweighted graph (every edge has equal cost), the answer is exactly what BFS computes. Because BFS visits vertices in increasing distance from the start, the first time we reach end is along a shortest path.
The trick is to enqueue each vertex along with its distance so far. Start with (start, 0). Each time you discover a new neighbor v from a vertex at distance d, enqueue (v, d + 1). When v == end, return d + 1.
Two edge cases. If start == end, the answer is 0. If BFS finishes without ever reaching end, the two are in different connected components, and the answer is -1.
Challenge
EasyWrite a function shortestPath that gets a 2D int array adjacency, an int start, and an int end, and returns the shortest distance (edge count) from start to end.
- If
start == end, return0. - If
endis unreachable fromstart, return-1. - Otherwise, return the minimum number of edges between them.
You must use the Graph class (provided in graph) - do not use language built-ins (maps, sets) to model the adjacency. Auxiliary data for the algorithm (visited sets, queues) may use stdlib types.
Try it yourself
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}