sksdong1   7년 전

알고리즘은 음수간선으로 만들고 벨만포드 n-1번 돌려서 최단거리 구하고,

이 과정에서 0으로 들어가는 간선은 종료간선이기 때문에 처리를 하지 않았습니다.

0으로 향하는 간선을 제외한 모든 간선이 완화되고,

각 정점에서 0으로 향할 수 있는 간선의 가중치를 자신의 거리에 대하여 가장 작은(음수로) 값을 찾구요

최종적으로 시작점과 연결을 해서 출력하는 형태인데


잘못된 부분이 어디있을까요?

zlzmsrhak   7년 전

확실하지는 않지만 0으로 들어오는 간선들 중에 중복간선이 있는 경우가 나오지 않을 것 같습니다.

41번째 줄에서 크기 비교를 하지 않고 넣기 때문에 큰 값이 무시될 수 있습니다.

sksdong1   7년 전

감사합니다 해결됬습니다.

댓글을 작성하려면 로그인해야 합니다.