Implementation of the graph algorithm DFS / BFS with some obstacles

Question

I would like to ask you if you can give me an advice about a task that is based on a graph algorithm - either DFS or BFS. There is a story behind the task. In the universe, there are a lot of planets. Some of these planets are infected by a dangerous virus that kills everyone. The task is to find a path from one planet to a planet where is a medicine and so it is possible there to cure people from the virus. To find the path is quite dangerous because of the virus. The crew may go to the planet where the virus is (they know in what planets the virus is), but they go there because they have no other option, since they have to find the medicine. On the planet that is infected the crew become infected and has some time to live (the time is a way from one planet to another planet). The result of this task should be a path from the start planet to a planet where there is the medicine. It should work for any map of known universe.

An example of a known universe with the planets. The starting planet is 0 and ending planet is 13. As you can see, the planets 1, 2, 4 are infected. In this specific example, there is one day to live after the crew become infected. So if the crew goes to the planet 1, they become infected and then on the next planet (4 or 6) dies. If they go to the planet 2, they become infected and they have just one day to live, so on the next planet dies... The result of this is the path 0 3 10 11 12 5 13.

An another example of a known universe with the planets. The starting planet is 0 and ending planet is 9. As you can see, the planets 4, 6, 7 are infected. In this specific example, there are two days to live after the crew become infected. So if the crew goes to the planet 4, they become infected and then after two days (one day = one way from one planet to another planet) dies. The result of this is either the path 0 1 2 3 5 7 6 9 or 0 1 2 3 5 7 8 9. As you can see, in some cases there might be more paths. The task is to find just one and it does not have to be the shortest one. Just one right path where the crew gets from start to end.

I have used the itterative DFS algorithm, but I do not know how to implement the part that if the crew would die on one path, the algorithm should find out another path. You can get it from the pictures of the graphs.

Answer 1

The easiest way to solve this problem is with BFS, but you start from the end.

Lets say the time to live after infection is TTL days.

Run BFS from the destination, but you can only consider going to infected planets on paths less than TTL long. Once the BFS hits a path with TTL length, then you can only use clean planets from then on, all the way to the start.

This is especially easy if you do the BFS level-by-level. Then you only need to check if level < TTL.

Answer 2

You can use use a shortest path algorithm like Dijkstra's algorithm for finding the shortest path between two nodes.

The edge weight is just the weight of the node you could be going to. In this case, all edges going to non-virus nodes would have a weight of 1. While edges going to a virus node would have a weight of number of nodes + 1. Visiting any virus planet should be easily more costly than visiting all other planets. This way the virus planets are only chosen if there is no other choice.

It also handles the case where you have to visit multiple virus planets, by preferring paths with the least amount of virus planets, not that it exactly matters in this case. Though if you want to list all equally valid solutions you could consider any additional virus planet as having a weight of 1 if the path already includes a virus planet. Then just display it as an another valid solution if it has the same weight as the best solution.

As for time to live, let's call it T, just check the current path. If the current node in the search is not the end node, and it has been T planets since the first virus planet crossed. Then reject the path as invalid.

An alternative handling for time to live would be to use an array weight, [path weight, virus age]. This means, given the same path weight, it will expand the path with the lowest virus age. Virus age is just # of days since exposed to virus.

Answer 3

You can do a modified BFS to solve this problem. While doing the BFS, maintain the number of days infected as a part of the state. Then, while traversing, accept traversing to a previously visited node if we would be visiting with a better number of infected days (i.e. less).

This will also be the shortest-path, since BFS will produce shortest path in a non-weighted graph.

Here's a quick sketch in Python, applied to your second example:

from collections import deque

def bfs(graph, virus_nodes, start, target, survive_days):
    survive_days = min(survive_days, len(graph)) 
    visited = {start : 0}
    queue = deque([(start, 0, (start,))]) # node, days infected, path

    while queue:
        node, days_infected, path = queue.popleft()
        is_infected = days_infected > 0 or node in virus_nodes

        nxt_days_infected = days_infected + 1 if is_infected else 0
        if nxt_days_infected > survive_days:
            continue

        for nxt in graph[node]:
            if nxt == target:
                return path + (target,)
            if nxt not in visited or visited[nxt] > nxt_days_infected:
                queue.append((nxt, nxt_days_infected, path + (nxt,)))
                visited[nxt] = nxt_days_infected

if __name__ == "__main__":
    graph = {
        0 : [1],
        1 : [0, 2], 
        2 : [1, 3], 
        3 : [2, 4, 5],
        4 : [3, 7], 
        5 : [3, 7],
        6 : [7, 9],
        7 : [4, 5, 6, 8],
        8 : [7, 9],
        9 : [6, 8],
    }
    virus_nodes = {4, 6, 7}
    max_survive_days = 2
    print(bfs(graph, virus_nodes, 0, 9, max_survive_days))

Output:

(0, 1, 2, 3, 5, 7, 6, 9)

Answer 4

If you don't care if it is shortest path you can use DFS with some adjustments to incorporate time to die feature. JSFiddle and code in javascript:

function findPath(path, infectedNodes, nodesBeforeDeath, initialNode, targetNode, adjacentTable) {
  const lastNode = path.visitedNodes[path.visitedNodes.length - 1];
  
  if (lastNode === targetNode) {
    return path;
  }

  if (path.nodesLeftBeforeDeath !== null && path.nodesLeftBeforeDeath !== undefined && path.nodesLeftBeforeDeath == 0) {
    return;
  }
 
  const adjacentNodes = adjacentTable[lastNode];
  
  for (const node of adjacentNodes) {
    if (path.visitedNodes.indexOf(node) > -1) {
        continue;
    }
    
    const newPath = {
        visitedNodes: [...path.visitedNodes, node]
    };
    
    if (path.nodesLeftBeforeDeath !== null && path.nodesLeftBeforeDeath !== undefined) {
        newPath.nodesLeftBeforeDeath = path.nodesLeftBeforeDeath - 1;
    }
    else if (infectedNodes.indexOf(node) > - 1) {
        newPath.nodesLeftBeforeDeath = nodesBeforeDeath;
    }
    
    const nodeResult = findPath(newPath, infectedNodes, nodesBeforeDeath, initialNode, targetNode, adjacentTable);
    
    if (nodeResult) {
        return nodeResult;
    }
  }
}

const firstExampleResult = findPath({
  visitedNodes: [0]
  },
  [1, 2, 4],
  1,
  0,
  13,
  [[1,2,3,4],
  [0,4,6],
  [0, 7, 8],
  [0, 9, 10],
  [0, 1, 11, 12],
  [6, 12, 13],
  [1, 5, 7],
  [2,6,14],
  [2,9,14],
  [3,8],
  [3, 11],
  [4,10,12],
  [4,5,11],
  [5],
  [7,8]]
);

console.log(firstExampleResult.visitedNodes);

const secondExampleResult = findPath({
  visitedNodes: [0]
  },
  [4, 6, 7],
  2,
  0,
  9,
  [
  [1],
  [0,2],
  [1,3],
  [2,4,5],
  [3,7],
  [3,7],
  [7,9],
  [4,5,6,8],
  [7,9],
  [6,8]
  ]
);
console.log(secondExampleResult.visitedNodes);