An inverse problem of the weighted shortest path problem (Q1894996): Difference between revisions

The paper discusses an inverse problem of the weighted shortest path problem as follows: Given a directed graph \(G(V, A)\), vertices \(a,b\in V\) and a path \(P\) from \(a\) to \(b\), find a weighted length vector \(w\geq 0\) such that \(P\) is a weighted shortest path from \(a\) to \(b\). It is pointed out that all such vectors form a polyhedral cone and a sufficient and necessary condition for vectors to solve the inverse problem is given. By showing algebraic and graphic characters of the extreme directions of the solution cone, the relation between this problem and the minimal cutset problem in graph theory is shown.