0
나는이 질문에 답해야하지만 어느 것이 더 유사한 지 모른다. dijkstra 알고리즘은 BFS뿐만 아니라 DFS와 몇 가지면에서 유사하다는 것을 알게되었습니다. 대답과 이유는 무엇인지 설명해 주시겠습니까? 감사!Dijkstra 알고리즘의 그래프가 DFS 또는 BFS와 더 비슷합니까?
A
답변
0
아니요.
다이크 스트라는 다이나믹 프로그래밍입니다 (dp[v] = min{dp[u] + w(u,v)} where u has already calculated and w(u, v) is the edge value).
욕심을 사용하는 것이 옳다는 것을 증명할 수 있습니다.
BFS와 DFS는 그래프를 검색하여 필요한 것을 얻는 방법입니다. 그러나 어떤 종류의 것들이 필요합니까?
모든 노드 값이 1 인 특정 노드와의 거리를 확인하려면 ok bfs가 Dijkstra의 특수한 경우입니다.
다른 알고리즘을 사용하거나 bfs 또는 dfs를 사용하여 다른 작업을 수행하려는 경우 dijkstra와 관련이 있거나 그렇지 않은 경우가 있습니다.
이것은 프로그래밍 관련 질문이 아닙니다. –
이러한 알고리즘과 비슷하지 않습니다. 그러나 모든 가장자리가 동일한 무게의 경우 dijkstra는 BFS와 유사한 방식으로 작동합니다. – Yerken
[최단 경로를 찾을 때 BFS와 다이 즘 트라의 알고리즘의 차이점은 무엇입니까?] (http://stackoverflow.com/questions/25449781/what-is-difference-between-bfs-and-dijkstras-algorithms-when - 짧은 뱃지) –