0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.