Задача китайского почтальона. В интернет-магазин по продаже часов в течение недели поступают заказы, а в выходные дни магазин доставляет бесплатно заказы клиентам. Пусть карта заказов на неделю представлена в виде взвешенной неориентированной сети G.

Задача китайского почтальона.

В интернет-магазин по продаже часов в течение недели поступают заказы, а в выходные дни магазин доставляет бесплатно заказы клиентам. Пусть карта заказов на неделю представлена в виде взвешенной неориентированной сети G. Магазин находится в вершине s, другие вершины – это перекрёстки, рёбра – улицы, на которых находится хотя бы один клиент, веса на рёбрах – длины улиц.

Требуется выбрать оптимальный (кратчайший) маршрут доставки товара клиентам магазина.