후면 모서리가있는 DFS 기반 변형은 실제로주기를 찾을 수 있지만 대부분의 경우 최소 가 아닙니다. 주기 . 일반적으로 DFS는주기가 있지만 실제로주기를 찾기에 충분하지 않다는 플래그를 제공합니다. 예를 들어, 두 개의 모서리를 공유하는 5 개의 다른 사이클을 상상해보십시오. 역 추적 변형을 포함하여 DFS 만 사용하여주기를 식별하는 간단한 방법은 없습니다.

Johnson의 알고리즘은 실제로 모든 고유 한 간단한주기를 제공하며 시간과 공간이 복잡합니다.

그러나 최소 사이클을 찾으려면 (정점을 통과하는 하나 이상의 사이클이 있고 최소 사이클을 찾는 데 관심이 있음을 의미 함) 그래프가 크지 않은 경우 아래의 간단한 방법을 사용해보십시오. Johnson에 비해 매우 간단하지만 다소 느립니다.

그래서, 하나 절대적으로 MINIMAL 사이클을 찾을 수있는 가장 쉬운 방법은 인접 행렬을 사용하여 모든 정점 사이의 최소한의 경로를 찾기 위해 플로이드의 알고리즘을 사용하는 것입니다. 이 알고리즘은 Johnson만큼 최적의 위치는 아니지만 너무 간단하고 내부 루프가 너무 작아서 작은 그래프 (<= 50-100 노드)의 경우에는 사용하는 것이 좋습니다. 부모 추적을 사용하는 경우 시간 복잡도는 O (n ^ 3), 공간 복잡도 O (n ^ 2), 그렇지 않은 경우 O (1)입니다. 우선주기가 있으면 질문에 대한 답을 찾으십시오. 알고리즘은 매우 간단합니다. 아래는 스칼라의 스 니펫입니다.

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

원래이 알고리즘은 가중치 에지 그래프에서 작동하여 모든 노드 쌍 사이의 모든 최단 경로 (따라서 가중치 인수)를 찾습니다. 제대로 작동하려면 노드 사이에 방향이 지정된 가장자리가 있으면 1을 제공하고 그렇지 않으면 NO_EDGE를 제공해야합니다. 알고리즘이 실행 된 후이 노드가 값과 동일한 길이의주기에 참여하는 것보다 NO_EDGE보다 작은 값이 있으면 기본 대각선을 확인할 수 있습니다. 동일한주기의 다른 모든 노드는 동일한 값을 갖습니다 (주 대각선).

사이클 자체를 재구성하려면 부모 추적과 함께 약간 수정 된 알고리즘 버전을 사용해야합니다.

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

부모 행렬은 처음에 꼭짓점 사이에 가장자리가 있으면 가장자리 셀에 소스 꼭짓점 인덱스를 포함해야하며, 그렇지 않으면 -1입니다. 함수가 반환 된 후 각 모서리에 대해 최단 경로 트리에서 상위 노드를 참조하게됩니다. 그런 다음 실제주기를 쉽게 복구 할 수 있습니다.

우리는 모든 최소한의 사이클을 찾기 위해 다음과 같은 프로그램을 가지고 있습니다.

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int],
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

결과를 테스트하는 작은 주요 방법

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

출력은

The following minimal cycle found:
012
Total: 1 cycle found