This paper addresses the shortest path problem for weighted interprocedural automata (WIPA), a simple model adapted to the analysis of low-level programs. We propose an efficient and versatile approach relying on Knuth’s generalization of Dijkstra’s algorithm to context-free grammars. Several variants of the problem are considered in the paper, depending on the starting and ending stacks. Moreover, we solve both the single-source and single-target versions. Each problem is translated into a succint context-free grammar, permitting the efficient computation of a solution in \(O(n \log n + m)\) time, where n and m are the number of states and transitions in the underlying WIPA. We provide experimental results on real-size programs showing the scalability of the approach.