1
$\begingroup$

I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two nodes in the graph, but considering that if there are more than one shortest path we return the path with the least number of nodes. I have already computed the minimum distances between any two nodes with the Bellman-Ford algorithm, and I'm having trouble with getting the shortest path with minimum number of nodes.

My approach so far is the following. Suppose we want to computer the shortest path from $u$ to $v$. For every node $s$ in the graph I look at the "next" possible nodes to the destination $v$ from $s$ by keeping a list of the minimizers $w^*$ of $$\min_{w \text{ is a neighbor of } s} (c(s, w) + \text{dist}(w, v)),$$ where $\text{dist}(w, v)$ is the minimum distance between $w$ and $v$ that I have already computed. This seems to me that it would give me all the shortest paths from $u$ to $v$ and I would just have to look at the one with least number of nodes, but I don't know how to iterate through them efficiently. Any ideas?

$\endgroup$
0

0

Browse other questions tagged or ask your own question.