给定如图所示的无向连通图，假定图中所有边权都为1，显然，从源点A到终点T的最短路径有多条，求不同的最短路径数目。
无向连通图
数据结构：
权值相同的最短路径问题，则单元点 Dijkstra 算法退化成 BFS 广度优先搜索，假定起点为0，终点N：
- 节点步数step[0,...,N-1]初始化为0；
- 路径数目pathNum[0,...,N-1]初始化为0；
- pathNum[0] = 1
算法分析：
若从当前节点 i 扩展到邻接点 j 时，
- 若step[j] = 0，则 step[j] = step[i] + 1, pathN[j] = pathN[i]；
- 若 step[j] = step[i] + 1, 则 pathN[j] += pathN[i]；
# !/usr/bin/env python
# -- coding: utf-8 --
# @Time : 2017/7/10 15:49
# @Author : Albert·Sun
# @Version : 0.10α-β
# @Description : 被python的浅复制坑了一把。。。
def findpath(grap):
step = [0]*len(grap)
pathn = [0]*len(grap)
pathn[0] = 1
queue = [0]
while len(queue) > 0:
node = queue.pop(0)
s = step[node] + 1
for i in range(1, len(grap)):
if grap[node][i] is 1:
if step[i] is 0 or step[i] > s:
step[i] = s
pathn[i] = pathn[node]
queue.append(i)
elif step[i] == s:
pathn[i] += pathn[node]
print 'Queue:', queue
print 'PathN:', pathn
return pathn
if __name__ == "__main__":
N = 16
grap = [[0] * N for i in range(N)] # 不能用[[0]*N]*N,浅复制
grap[0][1] = grap[0][4] = 1
grap[1][0] = grap[1][5] = grap[1][2] = 1
grap[2][1] = grap[2][6] = grap[2][3] = 1
grap[3][2] = grap[3][7] = 1
grap[4][0] = grap[4][5] = 1
grap[5][1] = grap[5][4] = grap[5][6] = grap[5][9] = 1
grap[6][5] = grap[6][2] = grap[6][7] = grap[6][10] = 1
grap[7][6] = grap[7][3] = 1
grap[8][12] = grap[8][9] = 1
grap[9][8] = grap[9][13] = grap[9][5] = grap[9][10] = 1
grap[10][9] = grap[10][14] = grap[10][6] = grap[10][11] = 1
grap[11][10] = grap[11][15] = 1
grap[12][8] = grap[12][13] = 1
grap[13][9] = grap[13][12] = grap[13][14] = 1
grap[14][13] = grap[14][10] = grap[14][15] = 1
grap[15][14] = grap[15][11] = 1
for i in range(N):
print grap[i]
print findpath(grap)
Python Demo 输出
注：可考虑扩展到结点N，则提前终止算法。
