skynet0149   6년 전

일단 문제는 해결하였습니다. 하지만 여기서 의구심이 드는 부분이 있습니다. 

저는 제일 처음에 INF 값을 200000000으로 초기화 하였습니다. 이유는 간선 개수가 200000개가 최대이고

거리의 최대값이 1000이기 때문에 이 두개의 값을 곱하여서 최대값으로 정해서 문제를 풀었습니다.

이렇게 정하는 것이 제대로 한것이 맞나요?? 다른 분들 같은 경우는 800에다가 1000을 곱하신 분들도 계시길래 여쭈어 봅니다.

그리고 제가 지금 풀긴 풀었는데 찝찝하여 이렇게 글을 씁니다. 저의 문제 접근 방법이 잘못된거 같기도 하여 이렇게 질문드립니다.

djm03178   6년 전

음수 또는 0 사이클이 없는 그래프에서, 최단 거리를 구할 때는 같은 정점을 2번 지날 일이 없습니다. 그래서 비록 간선의 개수가 20만개더라도, 실질적으로 최단경로에서 이용하게 되는 간선은 (정점의 수) - 1개밖에 되지 않습니다. 그래서 아무리 길어야 최단 거리가 800 * 1000을 넘을 일은 없습니다.

skynet0149   6년 전

그럼 방향성, 무방향성 또는 댓글에서 언급하신 부분을 제외하고는 거의 제가하는 방식이 아닌 정점의수 -1개로 생각하고 하면 되는건가요?

skynet0149   6년 전

제가 댓글위에 말을 잘못했네요 방향성, 무방향성 그래프에서 언급하신 부분을 제외하고 입니다.

djm03178   6년 전

만일 어떤 최단 경로가 정점의 수 이상의 간선을 거친다면, 비둘기집의 원리에 의해 적어도 하나 이상의 정점은 2번 이상 방문해야 합니다. 그런데 간선의 가중치가 전부 양수라면, 처음 방문했을 때까지의 거리에 비해 두 번째 방문했을 때는 그 거리가 늘어나야 합니다. 다익스트라 알고리즘의 원리를 생각해 보면, 이 경우에는 다시 방문을 하지 않는다는 것을 알 수 있고, 그래서 처음의 가정이 모순이 됩니다.

무방향성 그래프라는 것은 그냥 방향성 그래프의 모든 간선이 반대 방향으로도 쌍으로 존재한다고 생각하면 되고, 이 경우에도 결과는 같습니다.

skynet0149   6년 전

친절한 답변 정말 감사합니다.

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