다익스트라와 벨만-포드 차이에서
331
投稿した質問数 1
안녕하세요.
다익스트라는 에지의 가중치가 양수일때 출발노드에서 전체 각 노드까지의 최단거리,
벨만-포드는 특정 출발노드에서 다른 노드까지의 최단 경로 탐색, 음수 가중치가 있어도 수행 가능
이렇게 되어있는데, 벨만-포드에서 에지 사용 횟수를 강조하는 이유가 다익스트라는 출발 노드가 정해져있고, 벨만-포드는주어진 출발노드가 달라질수 있어서라고 생각하면 될까요..?
처음엔 가중치 양수, 음수만의 차이만 인줄 알았는데, 뭔가 강조하시는걸 보니 저런 이유때문인가하고 질문해봅니다..!
다들 화이팅
回答 2
0
안녕하세요, 인프런 AI 인턴입니다. 2885_님.
다익스트라 알고리즘과 벨만-포드 알고리즘의 차이와 에지 사용 횟수에 대한 궁금증을 갖고 계시는 것 같습니다.
다익스트라 알고리즘은 각 에지의 가중치가 양수일 때 사용하는 알고리즘으로 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 데 효과적입니다. 다익스트라는 또한 그리디 알고리즘으로, 각 노드에 대해 가장 가까운 노드를 우선적으로 탐색해 시간 복잡도가 낮으며, 특정 상황에서 최적의 결과를 보장합니다.
반면, 벨만-포드는 음수 가중치가 있는 경우에도 적합한 알고리즘으로, 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾을 수 있습니다. 벨만-포드에서는 각 에지에 대해 반복적으로 업데이트를 수행하여 최적의 경로를 탐색하는데, 이는 노드 수에 비례하는 에지 사용 횟수로 구현됩니다. 이러한 반복적인 업데이트가 가능한 이유는 주어진 경로에서 한 에지를 중복해서 사용할 수 있다는 점을 감안하기 때문입니다. 특히, 벨만-포드는 음수 사이클을 검출할 때 에지 사용 횟수의 중요성이 두드러집니다.
관련 논의가 진행된 게시물 몇 가지를 참조해보시길 추천드립니다:
- 백준 2178 미로탐색 질문 입니다.
- 백준 2251 C++ 질문 있습니다.
위 답변이 도움이 되었기를 바랍니다. 이해가 되지 않거나 추가적으로 궁금하신 부분이 있으시면 주저하지 말고 더 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
62강 노션 링크 사용권한 승인 부탁드립니다.
0
0
0
작업형 2 템플릿 확인 요청
0
5
1
실습 2인데 커서아이디 같은거 다운로드 안내같은건 따로없나요??
0
4
1
5. 실습 (1) 개발 환경 준비와 프로젝트 구조 03:11
1
7
1
코딩 문제 사이트 접속 오류
0
5
1
실행이 안 되는데요.
0
4
0
print 문법 실행 안 돼요.
0
5
1
작업형2 인코딩 질문
0
17
2
작업형 3 벼락치기 공부방법 질문
0
23
2
14강의 예시 데이터를 통한 답을 구하는 과정에서의 문의
0
7
1
영문 계정
0
8
1
기출 11회 작업형 2_전체 데이터 학습 여부
0
28
2
RateLimitError
0
14
2
예측값 결과 소수점 차이
0
24
2
여태까지 발견한 이슈들 공유드립니다.
1
29
1
기출 문제와 실전챌린지 연습문제 무엇부터 푸는게 나은가요?
0
29
1
전처리 train() test([ ])
0
20
2
작업형 1 배경지식 질문
0
26
2
옳게 풀은건지 질문드립니다!
0
19
1
병합정렬이 홀수개의 숫자에 적용될 경우?
0
124
0
나머지 합 구하기 핵심 아이디어 문의
0
231
1
Python sys.stdin.readline() 사용
0
547
1
17298 오큰수 구하기 질문있습니다.
1
695
2
디버깅에 관한 질문
1
654
1