假设在有向图中从起点到s，到终点t的最短路径长度为distance,，最短路径的条数为kinds。对于某条有向边E(i, j)，如果该条边一定被从s到t的最短路径经过，那么首先需要满足：dis(s, i)+dis(i, j) + dis(j, t) == dis(s, t);//其中dis(a, b)表示从a到b的最短路径
其次还需要满足kinds(s, i) + kinds(j, t) == kinds(s, t);//其中kinds(a, b)表示从a到b最短路径的条数。
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/ccsu_001/article/details/47667419