Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where weights of $ij \in E$ are calculated with CalculateEdgeWeight($ij$). Is there a shortest path algorithm that does not require the knowledge of all edge weights by the end of the algorithm so that the use of CalculateEdgeWeight is minimized? What if we have bounds on the possible weights?
Shortest path where weights are computationally expensive to calculate
shortest path
No, you may have to examine all of the edges. Consider a graph where $V=\{s,t,v_1,\ldots , v_n\}$ and $E=\{(s,v_1),\ldots,(s,v_n),(v_1,t),\ldots,(v_n,t)\}$. If $W(s,v_i)=1$ for all $i$, the problem is finding $i$ so that $W(v_i,t)$ is minimal. And we can not find the minimal $W(v_i,t)$ without examining all of them.Dijkstra's Algorithm/$A^*$ use a greedy strategy, in which they do not necessarily examine all edges but only those on a path from the source that is at most as long as the shortest path. You could further improve this by using bidirectional (meet-in-the-middle) variants.You could also use $A^*$ with a heuristic to take any bounds on the edge weights in to account. If you have a lower bound on the edge weights, you can first use BFS to compute minimum length path, and then use that times the lower bound to get a lower bound on the actual distance from any vertex to the goal.