An efficient Dijkstra-like labeling method for computing shortest odd/even paths (Q1072571)

The author investigates the problem of determining shortest even (odd resp.) paths in a graph \(G=(V,E)\). First, using the connections between matching and augmenting paths in \(G\), the theory of shortest augmenting path labeling method is developed. It yields \(O(| V|^2)\) procedure for finding the shortest even (odd resp.) path in \(G\) joining two specific nodes \(i\) and \(j\). Secondly, by means of the use of priority queues for storing path labels an \(O(| E| \log | V|)\) labeling method for shortest even paths is described and carefully analyzed.