728x90 SMALL Computer Science/Data Structure2 Dijkstra 알고리즘 δ(A, B) : A->B로 가는 최단경로 w(A, B) : A와 B 사이의 연결된 edge의 weight if) A와 B 사이에 연결된 edge의 weight = 5 -> w(A,B) = 5 if) A와 B 사이에 edge가 X -> w(A, B) = ∞ (갈 수 없으므로) Single-Source Shortest Paths 시작 정점(s)이 하나 주어졌을 때, s에서 다른 모든 노드로 향하는 shortest path를 찾는 문제 Dijkstra Algorithm - S라는 이미 방문한 정점들에 대한 set 유지 -> 처음엔 비어있고, 시작과 동시에 시작 정점이 s에 들어가게 된다. - D라는 distance array를 정점 수만큼 유지 -> D[i]는 현재까지 밝혀진 경로들 중 최단 경로 (d(s,.. 2023. 5. 23. BFS DFS DFS (1) 재귀로 호출 (2) stack 사용 (1) (2) 2개 코드 차이 BFS * 참고링크 https://www.youtube.com/watch?v=PMMc4VsIacU https://www.youtube.com/watch?v=xlVX7dXLS64 2023. 1. 22. 이전 1 다음 320x100 LIST
