虽然我还是初学者,但我喜欢解决与图形相关的问题(最短路径,搜索等).最近我遇到了这样的问题：
Given a non-directed,weighted (no negative values) graph with N nodes and E edges (a maximum of 1 edge between two nodes,an edge can only be placed between two different nodes) and a list of X nodes that you must visit,find the shortest path that starts from node 0,visits all X nodes and returns to node 0. There’s always at least one path connecting any two nodes.
Limits are 1 <= N <= 40 000 / 1 <= X <= 15 / 1 <= E <= 50 000
这是一个例子：
红色节点(0)应该是路径的开始和结束.您必须访问所有蓝色节点(1,2,3,4)并返回.这里最短的路径是：
0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 with a total cost of 30
我想过使用Dijkstra找到所有X(蓝色)节点之间的最短路径,然后贪婪地选择最近的未访问的X(蓝色)节点,但它不起作用(在纸上提出32而不是30).我后来也注意到,只找到所有X节点对之间的最短路径将花费O(X * N ^ 2)时间,这个时间太大而节点数量太多.
我唯一可以找到的电路是Eulerian电路,它只允许访问每个节点一次(我不需要它).这可以用Dijkstra解决,还是有其他算法可以解决这个问题？
