<span>最短路径条数问题</span>

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int N = 16;
 7 
 8 int CalcShortestPathNum(int G[N][N]){
 9     int step[N];//每个节点可以几步到达
10     int PathNum[N];//到每个节点有几种路径
11     memset(step,0,sizeof(int)*N);
12     memset(PathNum,0,sizeof(int)*N);
13     PathNum[0] = 1;
14     queue<int> q;//存储当前搜索的节点
15     q.push(0);
16     while(!q.empty()){
17         int cur = q.front();
18         q.pop();
19         int s=step[cur]+1;//到下一连通节点的步数
20         for(int i=1;i<N;i++){//0是起点，不需要遍历
21             if(G[cur][i]==1){//连通
22                 //没有达到或者没有更快的路径
23                 if((step[i]==0)||(step[i]>s)){
24                     step[i] = s;
25                     PathNum[i] = PathNum[cur];
26                     q.push(i);
27                 }
28                 //当发现相同的最短路径时
29                 else if(step[i]==s){
30                     PathNum[i] += PathNum[cur];
31                 }
32             }
33         }
34     }
35     return PathNum[N-1];
36 }
37 int main()
38 {
39     int G[N][N];
40     memset(G,0,sizeof(int)*N*N);
41     G[0][1] = G[0][4] = 1;
42     G[1][0] = G[1][5] = G[1][2] = 1;
43     G[2][1] = G[2][6] = G[2][3] = 1;
44     G[3][2] = G[3][7] = 1;
45     G[4][0] = G[4][5] = 1;
46     G[5][1] = G[5][4] = G[5][6] = G[5][9] = 1;
47     G[6][2] = G[6][5] = G[6][7] = G[6][10] = 1;
48     G[7][3] = G[7][6] = 1;
49     G[8][9] = G[8][12] = 1;
50     G[9][5] = G[9][8] = G[9][10] = G[9][13] = 1;
51     G[10][6] = G[10][9] = G[10][14] = G[10][11] = 1;
52     G[11][10] = G[11][15] = 1;
53     G[12][8] = G[12][13] = 1;
54     G[13][12] = G[13][9] = G[13][14] = 1;
55     G[14][13] = G[14][10] = G[14][15] = 1;
56     G[15][11] = G[15][14] = 1;
57     cout<<CalcShortestPathNum(G)<<endl;
58     return 0;
59 }