Package com.jgalgo

Interface ChinesePostman


  • public interface ChinesePostman
    An algorithm for the chinese postman problem.

    The chinese postman problem is to find a closed path that visits all edges in the graph at least once, with minimum weight sum with respect to a given edge weight function.

    The problem can be solved in polynomial time.

    Author:
    Barak Ugav
    • Method Detail

      • computeShortestEdgeVisitorCircle

        Path computeShortestEdgeVisitorCircle​(Graph g,
                                              WeightFunction w)
        Compute the shortest circuit that visits all edges in the graph at least once.
        Parameters:
        g - a graph
        w - an edge weight function
        Returns:
        a closed path that visits all edges in the graph, with minimum weight sum with respect to the given edge weight function