Блог

Пусть G = (V; E) — ориентированный граф с двумя весами we и re на каждом ребре e. В этом графе есть две специальные вершины: c, химический завод, и a, амфитеатр. Задача состоит в том, чтобы создать план эвакуации от a до v для каждой вершины w в V на случай, если на химическом заводе возникнет пожар. Время, необходимое для распространения огня вдоль ребра e, равно re. Время для перемещения по ребру — это мы.

Я должен написать алгоритм, чтобы найти кратчайший безопасный путь от a до v для каждого v в V: путь безопасен, если он не включает ни одной вершины в re во время прохождения этой вершины.

Мои попытки:

i. Я сначала вычислил время, в которое каждая вершина ловит огонь, предполагая, что химический завод ловит огонь в момент времени 0.

ii. Затем я модифицировал алгоритм Дейкстры так, чтобы он не использовал какую-либо вершину на re на путях, которые он вычисляет.

Мой алгоритм:

 DijkstraShortestPath:
       1. graph[][] --> read the graph
       2. c <-- chemical plant
       3. a <-- amphitheater  
       4. for i --> 0 to V   
            queuePriority.add(i);
            distance[i] = Integer.MAX_VALUE;
            prev[i] = -1;
            visitedVertex[i] = false;
        }
        5. Q <-- queue(c), level[]--> inifinity
        6. while Q is not empty:
              U <-- Q.pop() 
   for all edges from u to v in G.adjacentEdges(c)
           If level[v] --> inifinity:
            level[v] <-- level[u]   re
            Q.enqueu(v)       
        7. distance[a] = 0;
        while (!queuePriority.isEmpty()) {

            int u = minDistance();
            if (u == -1) {
                break;
            }

            queuePriority.remove(u);
            visitedVertex[u] = true;

            for (int i = 0; i < nodeNumber; i  ) {
                if (graph[u][i] != 0 amp;amp; graph[u][i]%re ==0 amp;amp; graph[u][i]   distance[u] < distance[i]) {
                    distance[i] = graph[u][i]   distance[u];
                    prev[i] = u;
                }
            }
        }
        printShortestPath(distination);
        return distance[distination];
    }
 

Решает ли мой алгоритм проблему? Если нет, как я могу изменить свой алгоритм для решения проблемы?