An algorithm for finding the essential sets of arcs of certain graphs

Given a graph and a weight function which associates to each path an element of a Q-semiring, an essential set of arcs is defined as the complement of a maximal set of arcs which can be removed from the graph without changing the weight of the optimal paths for any pair of vertices. Conditions are given under which a graph admits a unique set of essential arcs and an algorithm is proposed to test for this condition and find this set of arcs.