之前碰到的很多问题都可以归结为路径搜索问题，就是求两点之间的路经
1）是否存在路径
2）求任意一条路径
3）求所有路径
求是否有路径和任意一条路径的时候，和正常遍历一样，一个点被mark之后不再访问，因为如果这个结点到终点有路径，之前就应该结束了，没结束说明没路径，再访问也无益。是 O(n)的，对于求所有路径，usedInPath 在进入结点时候mark，退出结点时候unmark， 每个结点可能被多次访问，总体是O(n!)的。可以有一些剪枝，比如当一个结点退出时候如果是可以到达终点的，就可以把这个点的marked重置为false，意思是这个点到终点有路径，可以供其他结点扩展再次进入。如果一个结点返回没有到达过终点，其marked项保持true, 以后再也不用进入。
def allPaths(G, start, end):
marked, path, ans = [False] * len(G), [], []
def dfs(v):
marked[v] = True
path.append(v)
num = len(ans)
if v == end: ans.append(path[:])
else:
for w in G[v]:
if not marked[w]: dfs(w)
path.pop()
if len(ans) > num: marked[v] = False # if current node is connected to end, reopen it
dfs(start)
return ans
补充，这里的marked和经典dfs里用来防止重复遍历的marked不同，这里是用来防止进入环从而带来无限状态的，而不是防重。路径搜索本身的状态是个 n!的DAG，路径一直在增长，不可能回到之前的路径，不需要去重，只是有环的话会无限多。上面reopen 又用marked做剪枝，是业务语义层面的判断，既不是去重，也不是去环
bfs 求路径问题
1）维护前驱列表，最后还原
2）结点保存路径，存储要求比较高。
3）最短路径必须用bfs，如果是求所有最短路径，扩展到一个结点时候不是立即mark, 而是这一层之后统一mark，因为允许同层的其他结点也指向这个结点。
DAG上的路径搜索(有点类似二叉树上的问题 f(root) = g(f(left), f(right))，当前节点的解依赖于左右孩子上的解。
DAG上还有一种常见搜索，求DAG中最长的路径，例题是POJ最长雪道，以及leetcode 数字三角最长到底边路径。即没有起点和/或终点的路径搜索
一般用 记忆化搜索，递推关系：d[v] = max{ d[w] } + 1 where (v, w)属于边集E。注意是DAG，DAG就是一个结点沿着有向边走下去不会回到自己。雪道问题就是，沿着坡度降低的方向走，高度一直下降，不可能回到路径上任何一点，典型的DAG。
背包问题用路径搜索建模：（隐式图建模）
都是DAG，不可逆，一直在减少，不可能回到之前的状态。
1）用最少（最多）硬币凑给定面值V问题
顶点：需要凑的面值。
边：可以进行的状态转移，（可以进行的操作，aka, 选择一个面值的硬币）
问题：从顶点V 到 顶点0的最短（最长）路径问题问题。f[v] = min{ f[v - w[i]] } + 1
2）完全背包问题
顶点：剩余容量C
边：可以进行的状态转移（选择一个物品），边的权值为物品的价值
问题：从顶点C出发的权值和最大的路径，（无终点路径搜索）。f[c] = max{ f[i - V[i]] + W[i]}，假如已知图是DAG，那么最短带权路径可以用这个dp，而不只是djisktra
如果是必须刚好装满，则是从顶点C出发，到顶点0的最大路径问题（不带权的就是1，带权的就是权值）。
DAG下的最短路径径，当然可以用记忆化搜索，然而有一种最针对的方法
按拓扑序遍历节点，relax节点的每条边，最终d[i]和 prev[i]就是最短路径
最长路径求法：每条边的权值取反，然后按上述方法求最短路径，然后将结果d[i]取反
