Bfs

Given a weighted graph $G$ with $V$ vertices and $E$ edges, where all the weights are non-negative, and a source vertex $s$, the single-source shortest path problem consists of finding the distance from $s$ to all other vertices.

In this article, I describe the problem in a weighted and unweighted graph, as well as implementations using BFS for unweighted graphs and Dijkstra's algorithm for weighted graphs using an array and a priority queue.

There are many ways to traverse a graph. For example, through breadth-first search and depth-first search. Exploring it with a breadth-first search has interesting properties, like implicitly computing the distance from a source $s$ to all the reachable vertices. Exploring it with a depth-first search has properties related to edges, like finding back edges, forward edges, and cross edges.

This article has implementations for both BFS and DFS.