Path-Finding algorithms in Graphs:¶
Introduction¶
Previously we've explored how graphs can be explored using graph search algorithms such as BFS and DFS, in many applications especially in transportation and video games, where the enviornment is modeled as a connected graph, it's important to find the paths connecting two nodes optimizing the traversal, ie: the shortest path, however it isn't always very obvious since the connections between can differ by being weighted with the weight possibly being negative if not BFS can solve the problem, otherwise, Dijkstra's, Bellman-Ford, A* and a newest algorithm are all proposed solutions to this problem which we will explore.
Weighted graph¶
A graph $G=(E,V)$ can be weighted if there exists $w: E→\mathbb{R}$ that maps edges to a scalar value called the weight of the edge, if $(u,v) \notin E\text{, } w(u,v) = \infty$, the weight of a path is the sum of the weights of the edges along that path.
Shortest path¶
The shortest path in a weighted graph $G=(E,V,w)$ between two vertices $u,v$ is denoted by $\delta_G(u,v)$
Dijkstra's Algorithm¶
For this we consider that the weights are non-negative ie $w: E \rightarrow \mathbb{R}^+$
Dijkstra's property¶
Dijkstra's algorithm runs on a very simple idea, consider 3 cities, A,B,C and we want to travel from A to C in the shortest route which goes through B, then it is necessary therefore that this shortest route from A to C, includes the shortest route from A to B.
Analogously if the shortest path from vertices $u,v$ goes through vertex $w$, then it includes the shortest path from $u$ to $w$.
We know then that if there were many vertices $(w_i)_{i\leq|V|}$ connected to $v$ then the shortest route from $u$ to $v$ is the shortest route to the $w_i$ whose connecting edge to $v$ has the smallest weight.
Formally, we introduce Dijkstra's property:
Let's consider any partitioning of the vertices $V$ into $X$ and $Y=V\backslash X$ with $u \in X$, and let:
$$ p(v) ≡ min_{x\in X} (\delta_G(u, x) + w(x, v)) $$ then: $$ min_{y\in Y} p(y) = min_{y\in Y} \delta_G(u, y). $$
Algorithm's pseudocode:
pseudo
function Dijkstra(Graph, source):
for each vertex v in V:
dist[v] <-- INF
parent[v] <-- NULL
Q.add(v)
dist[source] <-- 0
while Q is not empty:
u <-- vertex u in Q with the minimum distance
Q.remove(u)
for each edge (u, v) in Q:
alt <-- dist[u] + Graph.E(u, v)
if alt < dist[v]:
dist[v] <-- alt
parent[v] <-- u
return dist[], parent[]
Dijkstra's algorithm original time complexity is $O(|V|^2)$, however it could be improved to $O(|E|+|V|\cdot log(|V|))$ using a Fibonacci heap priority queue as introduced in Fredman & Tarjan 1984
INF = 100000
def Dijkstra(graph, u):
n = len(graph)
distance = [INF] * n
parent = [-1] * n
visited = [False] * n
distance[u] = 0
for _ in range(n):
t = -1
min_dist = INF
for i in range(n):
if not visited[i] and distance[i] < min_dist:
min_dist = distance[i]
t = i
if t == -1:
break
visited[t] = True
for v in range(n):
if graph[t][v] > 0 and not visited[v]:
if distance[u] + graph[t][v] < distance[v]:
distance[v] = distance[t] + graph[t][v]
parent[v] = t
return distance, parent
graph = [
[0, 2, 0, 1],
[2, 0, 3, 0],
[0, 3, 0, 4],
[1, 0, 4, 0]
]
dist, parent = Dijkstra(graph, 0)
print("Distances:", dist)
print("Parents:", parent)
Distances: [0, 2, 5, 1] Parents: [-1, 0, 1, 0]
Bellman-Ford Algorithm¶
The Bellman-Ford algorithm is set to work even if the graph as negative weights as long as there are no cycles whose weights add up to a negative value ie:
$$ \forall (v_1,\dots,v_n,v_1) \in |V| , \sum_{i=1}^{n}w(v_i,v_{i+1})\geq 0 $$
Bellman-Ford algorithm's pseudocode:
pseudo
function BellmanFord(Graph, source):
for each vertex v in Graph.V:
dist[v] <- INF
parent[v] <- NIL
dist[source] <- 0
for i from 1 to |Graph.V| - 1:
for each edge (u, v) in Graph.E:
w <- weight(u, v)
if dist[u] + w < dist[v]:
dist[v] <- dist[u] + w
parent[v] <- u
for each edge (u, v) in Graph.E:
w <- weight(u, v)
if dist[u] + w < dist[v]:
print "Negative-weight cycle reachable from source"
return
return dist, parent
INF = 100000
def BellmanFord(graph, source):
n = len(graph)
distance = [INF] * n
parent = [-1] * n
distance[source] = 0
for _ in range(n - 1):
updated = False
for u in range(n):
for v in range(n):
w = graph[u][v]
if w > 0 and distance[u] != INF and distance[u] + w < distance[v]:
distance[v] = distance[u] + w
parent[v] = u
updated = True
if not updated:
break
has_negative_cycle = False
for u in range(n):
for v in range(n):
w = graph[u][v]
if w != 0 and distance[u] != INF and distance[u] + w < distance[v]:
has_negative_cycle = True
break
if has_negative_cycle:
break
return distance, parent, has_negative_cycle
graph = [
[0, 2, 0, 1],
[2, 0, 3, 0],
[0, 3, 0, 4],
[1, 0, 4, 0]
]
dist, parent, neg_cycle = BellmanFord(graph, 0)
print("Distances:", dist)
print("Parents:", parent)
print("Negative cycle?", neg_cycle)
Distances: [0, 2, 5, 1] Parents: [-1, 0, 1, 0] Negative cycle? False
While the Bellman-Ford algorithm eases the no negative weights constraint of Dijkstra's algorithm, it runs on a time complexity (in a worst case scenario) of $O(|V|\cdot|E|)$, considerably tasking compared to the latter.
Both algorithms find the shortest path from one source to every other node in the graph, but in most applications we want the shortest path from one source node to a goal node which is the concern of the A* star algorithm used in most real world and software applications and which we will develop and discuss in depth in the next article.