在bellman中模板一般都是这个样子 for(int k=1;k<=n-1;k++){ flag=0; for(int j=1;j<=m;j++) { if(dis[v[j]]>dis[u[j]]+w[j]) { dis[v[j]]=dis[u[j]]+w[j]; flag=1; } } if(flag==0) { break; }}但试一试这组测试数据: 6 52 4 -104 6 -102 5 -105 6 -103 6 -10结果输出了,但我们发现这个图根本不连通! 所以最短路算法(搜索除外)都应该判断1号点到u号点连不连通。
|