这个问题是前几天论坛wushibuzhi同学提出来的（ https://bbs.pinggu.org/thread-10540615-1-1.html ）本来可以直接回复他，后来考虑内容比较多，而且为更方便其他同学利用，因此这里新开一贴。

问题：计算从A到Z之间的最优时效路径

为此做了一个示例数据，如下：
[hide][/hide]




不考虑时间约束的网络图


使问题复杂化的是，从一个节点到下一个节点的行程时间如果超过下一个节点的出发时间，需要等一天，也就是相应的形成时间增加24小时，导致上面这个网络里的每条边的耗时是不确定的。

思路是这样的，针对有向网络，如果A出发可以去n个节点，比如可以去B，也可以去C，则将A拆成n个，A1去节点B，A2去节点C;其他节点同样处理，比如B1可以去C，B2可以去D。节点拆分后，edge也增加了，比如A1-B1, A1-B2 。这样处理后，我们就可以根据约束条件计算每一条edge的耗时，或者是标准时间，或者是标准时间+24 。然后即可以用igraph生成网络，并计算节点之间的最短路径。



调整后的网络图如下：



经过上述调整，我们可以计算最短路径


提醒：
1、上述网络是有向的；
2、上述代码只计算了从A到E的路径，计算其他区间点，需要对代码略作调整；

3、这种方式的缺点是，如果节点太多，可能会极大地增加计算量。