打开网易新闻 查看更多视频
深度优先搜索 寻路问题：
打开网易新闻 查看精彩图片
解题思路 从城市：1开始深度优先遍历整个图，找到所有能过到达 N 的走法， 选一个最优的。
从城市 1开始深度优先遍历整个图，找到所有能过到达 N 的走法， 选一个最优的。
优化： 1) 如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中，总长度已经大 于L的走法，就可以直接放弃，不用走到底了。
从城市 1开始深度优先遍历整个图，找到所有能到达 N 的走法， 选一个最优的。
优化： 1) 如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中，总长度已经大 于L的走法，就可以直接放弃，不用走到底了。
2) 用midL[k][m] 表示：走到城市k时总过路费为m的条件下，最优路径的长度。若在 后续的搜索中，再次走到k时，如果总路费恰好为m，且此时的路径长度已经超过 midL[k][m],则不必再走下去了。
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
热门跟贴