具有多个源和汇的寻路？

Question

我有一个最短路径问题需要解决，我相当确定应该有一个有效的解决方案我有一个有趣的图形表示：

ascii:

input

. N N N N N N
W 7 9 8 8 7 5 N . . . N N N
W 2 2 2 1 1 6 6 N N N 5 5 N E
W 1 2 3 2 2 2 2 4 5 5 4 2 5 E
. S S S 3 3 3 2 6 5 4 2 2 2 E
. . . . S S 2 2 2 2 3 7 2 2 E
. . . . . . S 2 3 2 7 7 7 7 E
. . . . . . . S 7 7 7 7 7 7 E
. . . . . . . S 7 7 7 S S 7 E
. . . . . . . . S 7 S . . S
. . . . . . . . . S

Output:
35

我需要找到从 'E' 个地点之一到 'W' 个地点之一的最短路径，走过编号的地点。我们无法在 'N' 和 's' 点上行走。当我们站在一个地方时，我们可以上下左右行走。我需要根据我正在行走的编号方块找到最短路径。这是一个更简单的例子：

我将创建一个双向 DAG，所有边都朝向编号边，该编号作为权重，所有边都朝向 E 或 W，权重为 0：

我的尝试

现在这是一个寻找从多个源到多个汇的最短路径的案例。我天真的想法是，我可以运行 Dijkstra 从每个 w 到每个 E。然而，这会运行类似 O(W*dijkstra^E) （其中 E 是 E 节点的数量）

有没有更聪明的方法来做多源多接收器 dijsktra？

Answer 1

一个解决方案是但需要转换为一个答案：运行一个普通的 BFS 但重新排队任何以前访问过的节点，这些节点可以以比以前想象的更低的成本到达。重新排队到访问节点的新发现的更便宜的路径让我们也可以重新计算它的邻居路径。

缺点是 BFS 将至少探索所有节点一次，因此最优性取决于您拥有的图的类型——如果它是一个相对于图的大小具有许多起点和终点的图，如你的例子，这很好，而运行宁多个 Dijkstra 变得有吸引力，因为源和汇的数量相对于图形的大小减少。

代码如下：

const findAllCoords = (G, tgt) => 
  G.reduce((a, row, ri) => {
    const res = row.reduce((a, cell, ci) => 
      cell === tgt ? [...a, [ci, ri]] : a
    , []);
    return res.length ? [...a, ...res] : a;
  }, [])
;

const shortestPathMultiSrcMultiDst = (G, src, dst) => {
  const key = ([x, y]) => `${x} ${y}`;
  const dstCoords = findAllCoords(G, dst);
  const visited = Object.fromEntries(
    dstCoords.map(e => [key(e), Infinity])
  );
  const neighbors = ([x, y]) =>
    [[0, -1], [-1, 0], [1, 0], [0, 1]]
    .map(([xx, yy]) => [x + xx, y + yy])
    .filter(([x, y]) => 
      G[y] && (!isNaN(G[y][x]) || G[y][x] === dst)
    )
  ;
  const q = findAllCoords(G, src).map(e => [e, 0]);
  
  while (q.length) {
    let [xy, cost] = q.shift();
    const [x, y] = xy;
    const k = key(xy);
    cost += isNaN(G[y][x]) ? 0 : +G[y][x];
    
    if (!(k in visited) || cost < visited[k]) {
      visited[k] = cost;
      q.push(...neighbors(xy).map(e => [e, cost]));
    }
  }

  return Math.min(...dstCoords.map(e => visited[key(e)]));
};

const G = `
. N N N N N N
W 7 9 8 8 7 5 N . . . N N N
W 2 2 2 1 1 6 6 N N N 5 5 N E
W 1 2 3 2 2 2 2 4 5 5 4 2 5 E 
. S S S 3 3 3 2 6 5 4 2 2 2 E
. . . . S S 2 2 2 2 3 7 2 2 E
. . . . . . S 2 3 2 7 7 7 7 E
. . . . . . . S 7 7 7 7 7 7 E
. . . . . . . S 7 7 7 S S 7 E
. . . . . . . . S 7 S . . S
. . . . . . . . . S
`.trim().split("\n").map(e => e.split(" "))
;
console.log(shortestPathMultiSrcMultiDst(G, "W", "E"));

OP 通过将所有源连接到一个节点并将所有接收器连接到一个节点，将问题简单地变成了一个常规的 Dijkstra 可解图，据我所知，这个解决方案几乎毫无意义。

Answer 2

经过深思熟虑，我想我自己想出了一个解决方案。接受的答案是完全有效和好的，但我认为应该运行比 A bfs 快，在最坏的情况下需要评估每个边缘 E 次。

这里是：我将所有 E 节点与源连接，边从源 (s) 到 E，权重为 0。所有 W 节点也连接到汇点 (t)，边从 W 到汇点。

这意味着之前显示的图表将如下所示：

现在我应该可以运行从 s 到 t 的常规 ol' dijkstra

具有多个源和汇的寻路？

pathfinding with multiple source and sinks?

algorithm

dijkstra

path-finding