UC知道图的最短路径条数？？？
来源：百度知道 编辑：UC知道 时间：2024/07/03 02:27:40
此题需要大家对图论的基本概念熟悉。
简单路径：不包含环的路径，称为简单路径。
最短路：在起点和终点之间的所有简单路径中，长度最短的路径。
路径的不同性：如果两条简单路径不包含相同的边，则称这两条路径不相同。
现在给你一个有向加权图，起点和终点，让你求出这两点之间有多少条不同的最短路。
Input
多组测试数据。
每组数据的第一行是一个整数N（2<= N<=100），表示图的顶点数，顶点编号为（0, 1, … N-1）。接着是一个N*N的矩阵G，代表输入的有向图。矩阵的元素G[i][j]表示从顶点i到顶点j是否有边，如果有边，则G[i][j]>0。
接下来一行是两个整数S，T（0<= S,T<=N-1；S!=T），代表起点和终点。数据保证没有自环
Output
每组数据输出一行。输出起点和终点之间不同最短路的最多的条数。
Sample Input
4
0 1 1 -1
-1 0 1 1
-1 -1 0 1
-1 -1 -1 0
0 3
5
0 1 1 -1 -1
-1 0 1 1 -1
-1 -1 0 1 -1
-1 -1 -1 0 1
-1 -1 -1 -1 0
0 4
Sample Output
2
1
在线等／／／／
简单路径：不包含环的路径，称为简单路径。
最短路：在起点和终点之间的所有简单路径中，长度最短的路径。
路径的不同性：如果两条简单路径不包含相同的边，则称这两条路径不相同。
现在给你一个有向加权图，起点和终点，让你求出这两点之间有多少条不同的最短路。
Input
多组测试数据。
每组数据的第一行是一个整数N（2<= N<=100），表示图的顶点数，顶点编号为（0, 1, … N-1）。接着是一个N*N的矩阵G，代表输入的有向图。矩阵的元素G[i][j]表示从顶点i到顶点j是否有边，如果有边，则G[i][j]>0。
接下来一行是两个整数S，T（0<= S,T<=N-1；S!=T），代表起点和终点。数据保证没有自环
Output
每组数据输出一行。输出起点和终点之间不同最短路的最多的条数。
Sample Input
4
0 1 1 -1
-1 0 1 1
-1 -1 0 1
-1 -1 -1 0
0 3
5
0 1 1 -1 -1
-1 0 1 1 -1
-1 -1 0 1 -1
-1 -1 -1 0 1
-1 -1 -1 -1 0
0 4
Sample Output
2
1
在线等／／／／
个人感觉用dijstra方法，由于是贪心，有可能在扩展的时候存在多条距离相同的边。我把它抽象为一棵树，由当前状态可以选择几条路径，就由其节点扩展为几个儿子。这样下来，最后得到的树有几个叶节点就有几条最短路径。
只是个想法，好像见过类似的题目，忘了怎么做了。感兴趣的话还可以研究一下求图有多少最小生成树和有多少生成树，两种完全不同的做法。