Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
The problem you are concerned with has been examined also in the literature. See the paper Szepesvári, C. 2004. Shorteset path discovery problems: A framework, algorithms and experimental results. Association for the Advancement of Artificial Intelligence 2004, pp. 550--555.. In this paper, the following is said at the very beginning:
In this paper we introduce and study Shortest Path Discovery (SPD) problems, a generalization of shortest path problems: In SPD one is given a directed edge-weighted graph and the task is to find the shortest path for fixed source and target nodes such that initially the edge-weights are unknown, but they can be queried. Querying the cost of an edge is expensive and hence the goal is to minimize the total number of edge cost queries executed.
Note that this work assumes edge costs to be unknown. A practical application of this theoretical assumption arise (as mentioned above) in those cases where querying the cost of an edge is very expensive ---as in your case. The algorithms considered in this paper are sound and they attempt at reducing the number of queries.
It seems, however, that your question also refers to the applicability of typical search algorithms such as A$^*$. Recall that A$^*$ expands all nodes $n$ such that $f(n)<f^*(s)$ where $f(n)=g(n)+h(n)$. In other words, it has to expand necessarily all nodes with an $f$-value which is lower than the cost of the optimal solution. The answer provided by Tom van der Zanden goes in this direction indeed. However, truth is that A$^*$ also generates (thus, it evaluates and stores in OPEN) a number of nodes with $f(n)\geq f^*(s)$ which are absolutely unnecessary.
This problem is of importance since the number of nodes generated grows exponentially with the depth of the search traversed. In your case it is twice importance because that extra amount of nodes have to be evaluated (and this requires querying a function its edge cost). A number of strategies have been proposed to save those extra generations in the context of A$^*$. For a good introduction and a plausible solution to this problem see: Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013 In case this paper fits your needs check the publications page by Ariel Felner because he also contributed with an additional paper.
Hope this helps,
