问题标题：
Dijkstra求最短路我已经明白了,但是次短路……次短路网上有多种做法：第一种枚举点u,找dist[u]+w(u,v)来查找到点v的次短路第二种：枚举点u,v找dist[u]+dist2[u2]+w(u,u2)查找次短路dist2指从终点到各
问题描述：
Dijkstra求最短路我已经明白了,但是次短路……
次短路网上有多种做法：第一种枚举点u,找dist[u]+w(u,v)来查找到点v的次短路
第二种：枚举点u,v找dist[u]+dist2[u2]+w(u,u2)查找次短路dist2指从终点到各个点的最短路,dist是起点.
第三种：做一遍dijkstra的时候同时记录最短路和次短路.
那么这三种里面哪些是对的,哪些是错的?求给出证明和详细解释.
孙革伟回答：
/**题目大意：*在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和;**算法思想：*用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路;*将dist数组开成二维的,即dist[v][2],第二...
点击显示
其它推荐