运筹学论文最短路问题

最短路问题一般建立在 赋权有向图 之上，如果是无向网，则可以将每条边写成两条单向弧以成为有向网。运筹学是研究达到目标的最优方法的学问，比如从A点到B点最短路径或者最快路径，需要先判断是要最短路径，还是要最快路径。决定了希望的结果后，才能根据此目标去研究方法。最短路问题（shortest-path-problem）是图论中的经典问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。基本内容是：假设网络中的每条边都有一个 权重（常用长度、成本、时间等表示），最短路问题的目标是找出 给定两点（通常是源节点和汇节点）之间总权重之和最小的路径。运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。

物流调度，这个用狄克斯拉标号法（D氏标号）貌似运筹学专门有一章就是求最短路的 ，比较好用，这个算法在管道路径选择。，设备更新，很实用的。不过运算量都挺大的，建议搜索下相关内容，认真看书把原理能透吧。

通过最小支撑树来求最短路的想法是不是认为求得了一个图的最小支撑树，则最小支撑树上任意两点间的链就是要求的最短路，这个没法保证的。以下引用一个别人的回答：在一棵最小生成树中，两点的距离在整个图中是最短的吗？？？不一定比如5个点连了一圈边 5个边中有四个长度1，一个长度2那么最小生成树是选4个长度为1的边但是长度为2的边连接的两个点之间最短路是2，没必要绕一圈。因此，对于最短路问题还是要使用Dijkstra算法，或者Ford算法

按三个原则

比如上面这个图，括号中给出的是初始流量。

V1发出6+10=16，V7收到7+3+6=16

V2收到6+3=9，发出6+3=9

V3收到10，发出3+0+7=10

V4/V5/V6亦是如此

你的图我看得有点模糊，你自己做一下即可。

这个我看不懂