Question

运筹学!最短路问题！

1. 如下图，S、A、B、C、D、E、T代表村镇，它们间连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路从S到T运输物品，应如何规划运行线路使路途最短。

Answer 1

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

Answer 2

g = Graph[{s <-> a, s <-> b, s <-> c, a <-> b, b <-> c, a <-> d,
b <-> d, c <-> e, b <-> e, d <-> e, d <-> t, e <-> t},
EdgeWeight -> {2, 8, 4, 2, 2, 7, 9, 8, 3, 2, 4, 7}];
Map[FindShortestPath[g, s, #] &, {a, b, c, d, e, t}]
Map[GraphDistance[g, s, #] &, {a, b, c, d, e, t}]
用Mathematica求得s到各点的最短路径：
{{s, a}, {s, a, b}, {s, c}, {s, a, d}, {s, a, b, e}, {s, a, d, t}}
s到各点的最短距离：{2., 4., 4., 9., 7., 13.}