Question

求“带限制条件的最短路径算法”用Dijstra算法的程序，要求：根据一个有向图来做不要太复杂时间复杂度小

Answer 1

dijstra算法是基于贪心思想的，有限制的话不一定可行～

Answer 2

什么限制条件？比如？？

追问

“给定起始节点和目标节点以及路径上要避开的节点列和必经节点列”这个限制条件来设计程序不要太复杂哦！

追答

dijkstra不太好做，至少我不会。
推荐你用spfa，它可以解决这道题。
避开的节点可以直接删掉与它相邻的边。
对于剩余的图，首先我们需要拆点。
对于点i，们拆成i和i'。如果i点是必经点，那么从i向i'连一条边权为-W(W>所有原图边权总和)，否则连一条边权为0的边。对于边i->j，变成i'->j。边权不变。
用spfa求出最短路，得到的ans+W*必经点数目就是解。(dijkstra不能求边权为负的最短路)
当然这样做有一种情况做不了，那就是必经点围成一个环。解决方法是用强连通分量缩点。
时间复杂度为O(kE) (spfa复杂度，不比dijkstra差)