문제 설정

가중 유방향 도표를 고려하다.가장자리의 무게가 마이너스일 수 있다고 가정해 보세요.
이 도표에 무거운 것과 마이너스의 순환이 포함되어 있는지 판단하는 방법을 고려한다.

예를 들어 위의 도표를 고려한다.위에는'2->1->3->4->2','2->3->4->2'두 개의 순환이 있다.
이 순환 계산의 가장자리의 무게는 각각 3, 0이기 때문에negative cycle가 존재하지 않습니다.
예를 들어'2->3'의 가장자리가 권중 2이면 후자의 순환은negative cycle이다.
그래프를 지정할 때, 이 그래프에negative cycle이 있는지 확인하십시오.어떻게 판정하면 좋을까요?

수법 1: Johnson's algorithm을 사용하여 모든cycle을 열거

천진스럽게 생각하면 도표의 모든 순환을 측정하고 그 무게를 계산하는 방법을 고려할 수 있다.
도표의 모든cycle 알고리즘을 열거하는 데 표준적인 것은Johnson's algorithm이다.
알고리즘의 세부 사항은 언급하지 않지만 예를 들어networkx를 사용하는 경우simple_cycles는 방법을 통해 얻을 수 있다.
networkx#simple_cycles

>>> import networkx as nx
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> G = nx.DiGraph(edges)
>>> list(nx.simple_cycles(G))
[[0, 2], [0, 1, 2], [0], [1, 2], [2]]

이 방법의 문제점은 일반적인 도표에 포함된cycle의 수량이 도표의 사이즈에 비해 지수가 증가한다는 것이다.조금 큰 차트라면 다루기 힘들 거야.
실제로 노드 수 30, 평균 횟수 3의 도표에도 순환이 매우 많은 것으로 나타났다.

>>> G = nx.erdos_renyi_graph(10,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
0
>>> G = nx.erdos_renyi_graph(20,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
62
>>> G = nx.erdos_renyi_graph(30,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
12869

수법2: Flowyd-Warshall algorithm

도표에 포함된cycle의 수량은 매우 많지만, 나는 마이너스crycle이 있는지만 알고 싶다.모든cycle을 열거할 필요가 없습니다.
이럴 때는 Flowyd-Warshall algorithm을 사용할 수 있다.Flowyd-Warshall algorithm은 차트에 포함된 모든 노드 대 사이의 최단 거리를 계산하는 알고리즘입니다.
Dijkstra 방법은 특정 노드 간 거리를 계산하는 방법이고 Flowyd-...모든 노드 대 사이의 가장 짧은 거리를 확정하는 방법이다.
또한 Dijkstra는 마이너스 무게를 가진 도표에 사용할 수 없지만 Flowyd-...무거운 짐을 지더라도 이용할 수 있다.
알고리즘의 설명은 wikipedia에서 설명하기 때문에 생략하지만 인접 행렬의 곱셈만 계산합니다.
(실제로 모든 원소 $A{ij}달러의 원소를 계산할 때 $\sum kA{ik}A{kj}달러를 계산하는 것이 아니라 $\mink(A{ik]+A{kj})달러를 계산한다.)
networkx 코드에서 본질적인 부분만 발췌해 보기 좋게 성형한 경우는 다음과 같다.

def floyd_warshall(G, weight='weight'):
    from collections import defaultdict
    dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
    for u in G:
        dist[u][u] = 0
    for u, v, d in G.edges(data=True):
        e_weight = d.get(weight, 1.0)
        dist[u][v] = min(e_weight, dist[u][v])  # self loopが正の重みを持つ場合があるので、minを取る必要がある
    for w in G:
        for u in G:
            for v in G:
                if dist[u][v] > dist[u][w] + dist[w][v]:
                    dist[u][v] = dist[u][w] + dist[w][v]
    return dist

노드 i, j의 (잠정) 최단거리 진입dist[i][j].
가장 바깥쪽 순환w에서 가장 짧은 거리를 업데이트합니다.w의 각 교체에서 w의 경로를 통해 u-v 간의 잠정적 최단거리를 업데이트할 수 있는지 확인하고 w를 통해 최단거리를 업데이트할 수 있다면 업데이트dist[i][j].
원가를 계산하는 것은 노드수의 3차원과 정비례한다.
이 알고리즘은negativecycle이 있는지 확인할 수 있습니다.dist의 대각선 원소가 마이너스라는 것을 알 수 있다.
디스트는 단조롭게 줄어들기 때문에 네거티브 스케일이 있는지 없는지만 확인하고 싶으면 최내 순환으로 판정하면 된다.
참조: S. Hougardy, "The Floyd–Warshall algorithm on graphs with negative cycles"

def has_negative_cycle(G, weight='weight'):
    from collections import defaultdict
    dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
    for u in G:
        dist[u][u] = 0
    for u, v, d in G.edges(data=True):
        e_weight = d.get(weight, 1.0)
        dist[u][v] = min(e_weight, dist[u][v])  # self loopが正の重みを持つ場合があるので、minを取る必要がある
    for w in G:
        for u in G:
            for v in G:
                if dist[u][v] > dist[u][w] + dist[w][v]:
                    dist[u][v] = dist[u][w] + dist[w][v]
                if u == v and dist[u][u] < 0:
                    return True
    return False