一类旅行总费用最小路线模型及其求解策略

旅行总费用最小路线问题是生活实际中常见的一类问题,本文建立了该类问题的赋权多阶段有向图模型。多阶段有向图是应用中常见的一种有向图,有许多运输、工程、管理等的实际问题能转化为有向图最短路问题进行求解,尤其赋权多阶段有向图对解决该类实际问题更具有重要意义。研究了赋权多阶段有向图的最短路问题,从图上逆序标号法、表上作业法和动态规划法不同的角度对文中模型给出了赋权多阶段有向图最短路求解策略。

A Shortest Path Model for the Most EconomicalTraveling and Its Solutions

The shortest path problem of the most economical traveling is popular practically.The multi-stage weighted directed graph model for the problem is set up.Multi-stage weighted directed graph is popular in application.Many practical issues such as transport,engineering,management can be solved by transforming into the shortest path problem.In particular,shortest path problem of the multi-stage weighted directed graph is more significance in solving such practical problems.In this paper,we study the shortest path problem of the multi-stage weighted directed graph and several solutions to it are presented by using an example from different perspective that is reverse labeling method on the graph,the tabular method and dynamic programming.