pathfinding with multiple source and sinks?

user_14444770 0
Viewed 423

I have a shortest path problem that I need to solve, and I'm fairly certain that there should be a efficient solution I have this fun representation of a graph:

as 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

I need to find the shortest a path from one of the 'E' spots to one of the 'W' spots, walking over the numbered spots. We are not able to walk on the 'N' and 's' spots. When we stand at a spot, we´re able to walk up, down,left and right. I need to find the shortest path in terms of the numbered squares that I am walking on. Here is a more simple example:

enter image description here

I would create a double directed DAG with all edges going towards a numbered edge, having that number as weight, and all edges going to E or W having weight 0:

enter image description here

my attempt

Now this is a case of finding a shortest path from multiple sources to muliple sinks. My naive thought is that I could run Dijkstra from every w, to every E. This would however run in something like O(W*dijkstra^E) (where E is the amount of E nodes)

Is there any smarter way to do a multi-source multi-sink dijsktra?

path-finding dijkstra algorithm
2 Answers

After giving this some thought, and I think I have come up with a solution myself. The accepted answer is completely valid and good, but I think should run faster than A bfs that in the worst case needs to evaluate each edge E times.

Here goes: I connect all E nodes with a source, with edges going from the source (s) to E, with weight 0. All W nodes are also connected to a sink (t), edges going from W to sink.

This means that the beforeshown graph will look like this:

enter image description here

Now I should be able just to run a regular ol' dijkstra from s to t

user_144447700

A solution was mentioned in the comments but bears conversion to an answer: run a normal BFS but re-enqueue any previously visited nodes which can be reached with lower cost than previously thought. Re-enqueing a newly-discovered cheaper path to a visited node lets us recompute its neighbor paths as well.

The downside is that BFS will explore all nodes at least once, so the optimality depends on the type of graph you have--if it's a graph with many starting and ending points relative to the size of the graph as in your example, this is good, whereas running multiple Dijkstra's becomes appealing as the number of sources and sinks diminishes relative to the size of the graph.

Here's the code:

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 shared a better answer that simply turns the problem into a regular Dijkstra-solvable graph by connecting all sources to a node and all sinks to a node, rendering this solution pretty much pointless as far as I can tell.

user_62433520
Related