相关疑难解决方法(0)

这是练习:

令v和w为有向图G =(V,E)中的两个顶点.设计线性时间算法以找到v和w之间的不同最短路径(不一定是顶点不相交)的数量.注意:G中的边缘未加权

对于这个消费税,我总结如下:

1. 这是一个有向图
2. 它询问不同最短路径的数量.首先,路径应该是最短的,然后可能存在不止一条这样的最短路径,其长度相同.
3. 在v和w之间,所以应该计算从v到w和从w到v.
4. 线性时间.
5. 图表未加权.

从以上几点来看,我有以下想法:

1. 我不需要使用Dijkstra算法,因为图表没有加权,我们试图找到所有最短路径,而不仅仅是单个路径.
2. 我维持一个count最短路径的数量
3. 我想首先使用BFS并保留global level信息
4. 我global level每次增加1,然后BFS达到一个新的水平
5. 我还保留了shortest level最短路径的信息
6. 我第一次在旅途中遇到w,我分配global level给shortest level和count++;
7. 只要global level等于shortest level,我count每次遇到w时都会增加.
8. 如果global level变得比大shortest level,我终止旅行,因为我正在寻找最短的路径而不是路径.
9. 然后我再次做2 - 8对于w

我的算法是否正确？如果我做v到w然后w到v,那还是被认为是线性时间吗？