网上找不到原题,是教练给的某不知名资料里的。
对于下图,假设起点为S,终点为T,从S到T的所有路径(包含复杂路径)的数量是?
答案是4,解析给出的解法是:利用下述矩阵自乘4次,S与T对应的数字为答案。
| S | A | B | C | D |
---|
S | 0 | 1 | 1 | 0 | 0 |
A | 0 | 0 | 1 | 1 | 1 |
B | 1 | 0 | 0 | 0 | 1 |
C | 1 | 0 | 0 | 0 | 0 |
D | 0 | 0 | 0 | 1 | 0 |
我这里有两个问题:
(1)复杂路径是什么?网上查不到这一个概念,而且这里如果理解成迹,那就会有无数条“路径”;
(2)解析中的解法的原理是什么?或者说为什么是正确的?
硬数只能数得出3条简单路径,S->A->T
、S->A->B->T
、S->B->T
希望可以有大犇答疑解惑m(_ _)m