안녕하세요. 강의 수강 중 궁금한 내용이 있어 질문 드립니다. 벨만 포드 알고리즘에서 첫 번째 반복문을 처음 실행했을 때 나오는 정답 리스트는 엄연히 말하면 [0,8,3,무한대,13] 인데 이는 강의에서의 "업데이트의 반복 횟수가 k번이라면 k개의 edge를 사용했을 때 각 노드들의 최단거리" 라는 설명과 모순되는 부분이 아닌가요?
용준님 안녕하세요 반갑습니다. 아마도 해방 부분은 ruclips.net/video/SaxPonfjV5M/видео.html 영상의 10:00 부터 보시면 답이 되시지 않을까 싶습니다. 이론적으로는 설명의 내용이 맞지만 실제로 for문을 통해 엣지를 순서대로 탐색을 하다보면 K개보다 더 많이 적용이 되는 경우가 생기게 됩니다. 예를들어 해당 영상의 샘플의 경우 5번노드는 엄밀히 이야기하면 2개의 에지를 사용하여 도착하지만 첫번째 반복문에서 2 -> 5 에지를 탐색하기전 1 -> 2 에지를 탐색하게 되기 때문에 한번의 반복문을 통해 5번까지의 최단 거리가 구해지게 됩니다. 구현 방식까지 고려하여 말씀을 드려보면 "업데이트의 반복횟수가 K번이라면 최악의 케이스라도 시작점을 기준으로 K개의 edge를 사용했을 때 도달 할 수 있는 모든 노드들의 최단거리를 구할 수 있고 노드의 개수가 N개인 경우 시작점에서 다른 노드에 도달할때 사용되는 edge의 개수가 최악의 케이스 일 때(한줄로 이어진 경우) N-1개이므로 N-1번의 반복문을 실행하면 어떠한 그래프던지 시작점과 다른 전체 노드 사이의 최단거리를 구할 수 있다." 로 말씀드릴 수 있을 것 같습니다. 도움이 되셨으면 좋겠습니다. 감사합니다. 좋은하루 되세요.
강의 감사합니다! 궁금한 점이 있는데, 시작점(1번노드)으로 업데이트하고 난 후, 왜 다시 1번 노드 부터 체크를 해야하나요? 굳이 이중 for문을 돌아야하는 이유가 있나요?.. 예를들어 제가 4개의 에지를 사용 했을 때 1번 노드가 음수가 될 수 있는 음수 가중치가 포함되어 있기 때문이라고 이해하는게 맞는 건지 궁금합니다
임예준님 안녕하세요. 반갑습니다. 문의해주신 내용을 정확하게 파악하지 못하여 다른 답변을 드릴 수 도있지만, 말씀을 드려보면 벨만포드에서 바깥쪽 포문은 몇개의 엣지를 이용한 최단거리인가?로 생각해 주시면 좋고 안쪽의 포문은 모든 노드를 도는 for문이라고 생각해주시면 됩니다. 최초 이중 포문에 도달하여 안쪽 포문을 한번 돌게 되면 각 노드에서 1개의 에지로 갈 수 있는 최단거리가 나옵니다. (여기가 헷갈릴 여지가 많은데, 정확하게 이야기하면 시작점에서 1개의 에지를 사용하여 갈 수 있는 각 노드의 최단거리입니다. ) 그리고 바깥쪽 포문을 통해 다음 안쪽 포문이 다시 돌게 되면 코드는 같지만 잘 생각해보면 2개의 에지를 사용하여 시작점에서 갈 수 있는 각 노드의 최단거리가 됩니다. 왜냐면, 최초 설정을 시작노드를 0, 나머지를 무한대로 놓고 진행하게 되는데 최초 포문이 돌면 시작노드에서 에지 하나로 갈 수 있는 노드들이 무한대에서 특정 값으로 업데이트가 됩니다. 때문에 그다음 안쪽 포문을 다시 돌때에는 같은 로직이더라도 기존에 무한대였던 노드들이 에지 하나로 갈 수 있는 노드들은 특정 값으로 변해있습니다. 그러면 이 노드들에서 다시 체크를 하면 이번에는 이 노드에서 파생되는 노드 ( 2개의 에지를 사용하여 갈 수있는 노드)들이 업데이트가 됩니다. => 아마도 이 부분을 다시 1번 노드부터 체크한다고 이야기해주신것 같습니다. 이런 식으로 전체 노드 개수의 -1 개 만큼 반복을 해주면 (바깥쪽 포문) 음수 사이클이 없다고 가정하고 벨만포드 최단거리가 완성되게 됩니다. 주말 마무리 잘하시고 행복하세요 :)
예제에서 1에서 3으로 가는 최단 거리를 구한다고 치면 3->1로 가는 음의 가중치 엣지가 하나 더 있으면 N이 5이니 4번 돌리면 2번 왔다갔다 하는 음수 사이클(1->3-1>-3)을 탈 것 같은데 그러면 의도했던 정답이 아닐 것 같은데... 이러면 5번 이상 안돌려도 음수 사이클을 타지 않나요? 벨만포드를 사용할 수 있는 그래프꼴이 따로 있는건가요?
안녕하세요. 반갑습니다. :) 제가 질문을 정확하게 이해하지는 못한것 같지만 설명을 드려보면 벨만포트 알고리즘은 음수 가중치가 있는 사이클의 최단거리를 구하는 알고리즘입니다. 단 말씀하신대로 음수사이클이 존재하게 되면 실제 최단거리는 해당 음수사이클을 돌수록 계속 작아지기 때문에 최단거리를 구하는 것이 불가능합니다. 다만 실제 문제들은 이러한 음수사이클을 찾아내는 것을 유도하는 경우가 많이 있습니다. 즉 벨만포트 알고리즘은 음수가중치가 있는 그래프의 최단거리를 찾거나 (음수사이클이 없는경우) 아니면 음수사이클 유무를 찾아내는 알고리즘이 됩니다. 5번이상 안돌려도 음수사이클을 타지 않나요?
@@codingtest 아 답변 감사합니다. 저는 벨만포드 알고리즘이 음수 사이클이 존재한다고 해도 특정 최단 경로에서 모든 간선을 1번 이하로 사용하여서 모든 정점의 최단거리를 구하는 방법이라고 착각해서 나온 질문이었습니다. 그 뒤에 다른 블로그랑 자료들도 찾아봤는데 말씀 해주신 것처럼 음수 사이클을 탄 이후에서의 최단거리를 상정한 알고리즘이 아니었네요. 답변 감사합니다. 책 잘 읽고 있습니다!
장세웅님 안녕하세요 반갑습니다. 보통 노드를 중심으로 풀이가 되는 알고리즘은 인접리스트를 사용하고 엣지를 중심으로 풀이가 되는 알고리즘은 엣지리스트를 이용하여 풀이하는 것으로 알고있습니다. 그리고 엣지리스트를 사용하는 알고리즘은 벨만포트, MST 정도가 있습니다. 유명한 알고리즘이고 풀이가 어느정도 일관되어 있기 때문에, 인접리스트로 예외처리를 잘하고 구현을 완벽하게 하시면 가능 할 수도 있을 것 같긴하지만 굳이 추천드리지는 않습니다. 감사합니다. 좋은하루 되세요 :)
이제 이해가 잘 되네요 명강의 감사드립니다! ❤
책만 봐서는 헷갈렸는데 설명 덕분에 잘 이해했습니다 감사합니다!
감사합니다! 다른데서 들을 수 없었던 설명을 듣고 갑니다. 벨만 포드 알고리즘에 대한 이해가 더 명료해지네요!
감사합니다 !!
안녕하세요. 강의 수강 중 궁금한 내용이 있어 질문 드립니다.
벨만 포드 알고리즘에서 첫 번째 반복문을 처음 실행했을 때 나오는 정답 리스트는 엄연히 말하면 [0,8,3,무한대,13] 인데 이는 강의에서의 "업데이트의 반복 횟수가 k번이라면 k개의 edge를 사용했을 때 각 노드들의 최단거리" 라는 설명과 모순되는 부분이 아닌가요?
용준님 안녕하세요 반갑습니다.
아마도 해방 부분은 ruclips.net/video/SaxPonfjV5M/видео.html 영상의 10:00 부터 보시면 답이 되시지 않을까 싶습니다.
이론적으로는 설명의 내용이 맞지만 실제로 for문을 통해 엣지를 순서대로 탐색을 하다보면 K개보다 더 많이 적용이 되는 경우가 생기게 됩니다.
예를들어 해당 영상의 샘플의 경우 5번노드는 엄밀히 이야기하면 2개의 에지를 사용하여 도착하지만
첫번째 반복문에서
2 -> 5 에지를 탐색하기전 1 -> 2 에지를 탐색하게 되기 때문에 한번의 반복문을 통해 5번까지의 최단 거리가 구해지게 됩니다.
구현 방식까지 고려하여 말씀을 드려보면
"업데이트의 반복횟수가 K번이라면 최악의 케이스라도 시작점을 기준으로 K개의 edge를 사용했을 때 도달 할 수 있는 모든 노드들의 최단거리를 구할 수 있고
노드의 개수가 N개인 경우 시작점에서 다른 노드에 도달할때 사용되는 edge의 개수가 최악의 케이스 일 때(한줄로 이어진 경우) N-1개이므로 N-1번의 반복문을 실행하면
어떠한 그래프던지 시작점과 다른 전체 노드 사이의 최단거리를 구할 수 있다."
로 말씀드릴 수 있을 것 같습니다.
도움이 되셨으면 좋겠습니다.
감사합니다.
좋은하루 되세요.
@@codingtest 단지 업데이트가 빨리 되는 것이고 알고리즘의 최종 결과에는 영향을 끼치지 못하네요!
빠른 답변 감사합니다!!
설명 너무 친절해요! 간지러운 데가 다 긁어진 기분 ㅎㅎㅎ😆
강의 감사합니다! 궁금한 점이 있는데, 시작점(1번노드)으로 업데이트하고 난 후, 왜 다시 1번 노드 부터 체크를 해야하나요? 굳이 이중 for문을 돌아야하는 이유가 있나요?.. 예를들어 제가 4개의 에지를 사용 했을 때 1번 노드가 음수가 될 수 있는 음수 가중치가 포함되어 있기 때문이라고 이해하는게 맞는 건지 궁금합니다
임예준님 안녕하세요. 반갑습니다.
문의해주신 내용을 정확하게 파악하지 못하여 다른 답변을 드릴 수 도있지만, 말씀을 드려보면
벨만포드에서 바깥쪽 포문은 몇개의 엣지를 이용한 최단거리인가?로 생각해 주시면 좋고
안쪽의 포문은 모든 노드를 도는 for문이라고 생각해주시면 됩니다.
최초 이중 포문에 도달하여 안쪽 포문을 한번 돌게 되면 각 노드에서 1개의 에지로 갈 수 있는 최단거리가 나옵니다.
(여기가 헷갈릴 여지가 많은데, 정확하게 이야기하면 시작점에서 1개의 에지를 사용하여 갈 수 있는 각 노드의 최단거리입니다. )
그리고 바깥쪽 포문을 통해 다음 안쪽 포문이 다시 돌게 되면 코드는 같지만 잘 생각해보면 2개의 에지를 사용하여 시작점에서 갈 수 있는 각 노드의 최단거리가 됩니다.
왜냐면, 최초 설정을 시작노드를 0, 나머지를 무한대로 놓고 진행하게 되는데 최초 포문이 돌면 시작노드에서 에지 하나로 갈 수 있는 노드들이 무한대에서 특정 값으로 업데이트가 됩니다. 때문에 그다음 안쪽 포문을 다시 돌때에는 같은 로직이더라도 기존에 무한대였던 노드들이 에지 하나로 갈 수 있는 노드들은 특정 값으로 변해있습니다.
그러면 이 노드들에서 다시 체크를 하면 이번에는 이 노드에서 파생되는 노드 ( 2개의 에지를 사용하여 갈 수있는 노드)들이 업데이트가 됩니다.
=> 아마도 이 부분을 다시 1번 노드부터 체크한다고 이야기해주신것 같습니다.
이런 식으로 전체 노드 개수의 -1 개 만큼 반복을 해주면 (바깥쪽 포문) 음수 사이클이 없다고 가정하고 벨만포드 최단거리가 완성되게 됩니다.
주말 마무리 잘하시고 행복하세요 :)
@@codingtest 이해했습니다 감사합니다~!
벨만포드 강의 감사합니다 :D
언젠가 C#언어로도 볼수 있었으면 좋겠네요~감사합니다.
연산 중간에 무한대에서 작은 수로 업데이트가 되면, 그 노드에서 출발하는 에지에 대해서는 (해당 for loop이 완료 안 되었을 때) 연산해줄 수 있게 되는 것인가요?
아 실제 코드에서는 연산을 해주지만 이론에서는 안 한다 이 말이군요 알겠습니다.
예제에서 1에서 3으로 가는 최단 거리를 구한다고 치면
3->1로 가는 음의 가중치 엣지가 하나 더 있으면 N이 5이니 4번 돌리면 2번 왔다갔다 하는 음수 사이클(1->3-1>-3)을 탈 것 같은데 그러면 의도했던 정답이 아닐 것 같은데...
이러면 5번 이상 안돌려도 음수 사이클을 타지 않나요?
벨만포드를 사용할 수 있는 그래프꼴이 따로 있는건가요?
안녕하세요. 반갑습니다. :)
제가 질문을 정확하게 이해하지는 못한것 같지만 설명을 드려보면
벨만포트 알고리즘은 음수 가중치가 있는 사이클의 최단거리를 구하는 알고리즘입니다.
단 말씀하신대로 음수사이클이 존재하게 되면 실제 최단거리는 해당 음수사이클을 돌수록 계속 작아지기 때문에 최단거리를 구하는 것이 불가능합니다.
다만 실제 문제들은 이러한 음수사이클을 찾아내는 것을 유도하는 경우가 많이 있습니다.
즉 벨만포트 알고리즘은 음수가중치가 있는 그래프의 최단거리를 찾거나 (음수사이클이 없는경우) 아니면 음수사이클 유무를 찾아내는 알고리즘이 됩니다.
5번이상 안돌려도 음수사이클을 타지 않나요?
@@codingtest 아 답변 감사합니다. 저는 벨만포드 알고리즘이 음수 사이클이 존재한다고 해도 특정 최단 경로에서 모든 간선을 1번 이하로 사용하여서 모든 정점의 최단거리를 구하는 방법이라고 착각해서 나온 질문이었습니다.
그 뒤에 다른 블로그랑 자료들도 찾아봤는데 말씀 해주신 것처럼 음수 사이클을 탄 이후에서의 최단거리를 상정한 알고리즘이 아니었네요.
답변 감사합니다. 책 잘 읽고 있습니다!
엣지 리스트로 설명 해주셨는데, 인접 리스트를 사용하면 안되는 건가요?!
장세웅님 안녕하세요 반갑습니다.
보통 노드를 중심으로 풀이가 되는 알고리즘은 인접리스트를 사용하고
엣지를 중심으로 풀이가 되는 알고리즘은 엣지리스트를 이용하여 풀이하는 것으로 알고있습니다.
그리고 엣지리스트를 사용하는 알고리즘은 벨만포트, MST 정도가 있습니다.
유명한 알고리즘이고 풀이가 어느정도 일관되어 있기 때문에,
인접리스트로 예외처리를 잘하고 구현을 완벽하게 하시면 가능 할 수도 있을 것 같긴하지만 굳이 추천드리지는 않습니다.
감사합니다. 좋은하루 되세요 :)