Блог

Нам предоставляется неориентированный граф, исходный узел, узел назначения и вес дополнительного ребра, который вы можете использовать для соединения любых двух узлов, которые не были подключены ранее. Вы должны найти минимальный вес возможного пути между источником и пунктом назначения. Предоставленное ребро можно использовать только один раз. Вот пример : граф с 5 ребрами следующим образом: 1-> 2 вес равен 1,2-> 3 вес равен 2,3-> 4 вес равен 3,4->5 вес равен 1,1->4 вес равен 3, а исходной вершиной является вершина 1, конечным пунктом — вершина 4. Мы должны указать, что минимальная длина пути. (в данном случае это 2) Мы можем использовать добавление дополнительного ребра весом 1 (здесь от 1 до 5) Я хотел бы знать, как это может быть реализовано на java.

Если я правильно понимаю вопрос, то все, что вы ищете, это реализация поиска в ширину в Java, которую можно найти здесь . и я не вижу никакой пользы для дополнительного веса ребра (поскольку это просто увеличило бы расстояние), если вы не используете дополнительное ребро для создания прямого пути между 1 и 4. (т. Е. источником и пунктом назначения), поэтому кратчайшее расстояние станет 1. Но опять же, вам пришлось бы проверять в каждом случае, имеет ли это дополнительное ребро вес, меньший, чем достигнутый при поиске в ширину. Кроме того, без использования дополнительного ребра кратчайшее расстояние в этом случае равно 3, а не 2.

Давайте предположим, что у вас нет нулевых и отрицательных ребер. Вы сохраняете ребра в массиве a[N][ N]. Немного измените график:

• создайте ориентированный граф из исходного графа:

   for (int i = 0; i < N; i  )
      for (int j = 0; j < N; j  )
          if (a[i][j] > 0 amp;amp; a[j][i] == 0)
              a[j][i] = a[i][j];
    

• сделайте копию графика и добавьте дикое ребро (дикое ребро направлено, ведет из части A в часть B, имеет заранее определенный вес)

• определите массив b: int b[2*N][2*N], инициализируйте ребра нулями

   for (int i = 0; i < N; i  )
      for (int j = 0; j < N; j  )
          if (a[i][j] == 0) {
              b[i][N j] = wildWeight;
          } else {
              b[i][j] = a[i][j];
              b[N i][N j] = a[i][j];
          }   
    

Найдите в Google реализацию алгоритма Дейкстры на Java и используйте его на этом промежуточном графике.