title: 如何判断图中两点间的路径条数？
desc: 遇到一笔试题，题目如下：<br>给你一个<b>有向图<b>，N点M边，问从1号点<b>出发<b>到N号点<b>截止<b>有多少条路径？<br><br>这道题坑挺多的：<br>（1）有可能有环，此时答案是无穷多，但只要走到N号点就不能再走，因此诸如<br>1-5-2-3-4-5-2-3-4.....N5的循环不算。<br>（2）有可能1点和N点不连通，此时答案是0<br>（3）有可能有多重边自环。<br>我的思路是：<br>（1）建图的同时构建反向图，即有向边全部反向得到的图。首先判断1到N之间有没有环，从1点开始dfs搜到n点，用染三种颜色的方法<br>（2）如果没有环，则令dpi表示从1到i的路径条数，因此<img src
topic: 算法
content: 此类问题首先想到的是经典的传递闭包，使用 Floyd-Warshall 算法可以容易的计算出所有点对间的最短路径连通性（传递闭包）以及路径数量，只需要在DP转移方程中分别使用minor和sum函数即可。然而，进一步想到（其实题主已经发现），有环时答案是正无穷，那么可以用经典DFS判环，如果无环则得到一个DAG，类似地改造DAG上的最短路算法来统计路径数题主的想法已经很接近了，但缺少关键一步必须按照拓扑序进行DP。至此
answerer_tags: Hexcles / Programmer / (Wanna be) Hacker