New answers tagged shortest-path
1
3).. . Also at each step I disregard the roads that has been travelled already for that particular path.
In order to do that, you must be running Dijkstra on a graph with exponentially more vertices than the input graph.
1
The Grassfire algorithm only works on a particular kind of graph; Dijkstra's algorithm works on any graph.
0
Your algorithm builds a tree, not a single path.
1
Your dynamic program is a step in the right direction.
My idea would be to maintain two values for a node v:
$L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases)
$U_v$: and the longest path in the subtree of v (i.e., case 3).
You already gave the formula for $L_v$.
For $U_v$ you take ...
Top 50 recent answers are included
