[Math] Algorithm to compute the shortest path in a weighted directed graph

Question

I'm trying to solve a short paths practice problem and I've encountered this. I have no idea how to approach it, can anyone help me? A thorough guide would be appreciated, I'm having a hard time thinking about this.

Discuss an efficient algorithm to compute
a shortest path from node s to node t in a weighted
directed graph G such that the path is of minimum
cardinality among all shortest s – t paths in G

Answer 1

Use the Bellman-Ford algorithm. In addition to recording the distance (i.e. the sum of all edge weights on the current estimated shortest path) and predecessor for each node, also record in a third array the cardinality (of the current estimated shortest path).

In the initialization step, initialize the cardinality for all nodes except s to $\infty$. Set the cardinality of s to 0.

for each vertex v in vertices: distance[v] := inf cardinality[v] := inf predecessor[v] := null distance[s] := 0 cardinality[s] := 0

Then, in the relaxation step, relax an edge if it will produce a shorter path (i.e. if the sum of all edge weights will be smaller), or if both paths are equally short (in terms of sum of edge weights) but one has lower cardinality (fewer edges) than the other. And when you relax an edge, update the cardinality for the destination node of that edge in addition to the distance and predecessor information.

for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: dist_thru_this_edge := distance[u] + w card_thru_this_edge := cardinality[u] + 1 if (dist_thru_this_edge < distance[v]) or (dist_thru_this_edge = distance[v] and card_thru_this_edge < cardinality[v]): distance[v] := dist_thru_this_edge predecessor[v] := u cardinality[v] := card_thru_this_edge

Then, check for negative weight cycles (code is the same as shown in the Wikipedia article). If there are none, the length of the shortest path is distance[t], its cardinality is cardinality[t], and the path can be traced back from t to s using the predecessor array (i.e. the predecessor of t on the shortest path is predecessor[t], the predecessor of that node is predecessor[predecessor[t]], and so on). Remember that predecessor[s] is null and this is not true for any other node once the shortest path has been found.