똑똑한 코드 작성을 위한 실전 알고리즘

257

7

장

그래프

매사추세츠주의 서쪽 끝 (뉴욕 경계)에서 동쪽 끝 고속도로(코드곶

9

)까지 최단 경로를 결정하

기 위해, 너비 우선 탐색을 사용해

236

.

5

마일을 계산한다([그림

7

-

14

]에 표시된 경로). 해당

99

-간선 경로는 보스턴의

I

-

90

/

I

-

93

고속도로 위에 식별된 경유지를 통과하고

총 간선 개수

측면에서 최단 경로 (시작에서 목적지까지 )가 된다. 하지만 간선의 가중치를 고려할 때 누적된

마일은 최단 경로라고 할 수 있을까? 답은 그렇지 않다는 것이다.

우리는 깊이 우선 탐색이 경로의 길이를 보장하지 않음을 알고 있다. [그림

7

-

15

]는 깊이 우

선 탐색으로 생성된

267

개 간선으로

485

.

2

마일을 이동한 것을 보여준다. 유도 탐색 알고리즘

은 여정 초기에 잘못된 결정을 내려 (그림에는 나타나지 않는다 )

141

개 간선,

245

.

2

마일을 계

산한다. [그림

7

-

14

]에서 또 다른 경로는 남동쪽 방향으로 진행하며

128

개 간선을 포함하고

210

.

1

마일만을 필요로 한다.

다익스트라 알고리즘

Dijkstra

algorithm

은 이 해결책으로 계산하는 방법

을 보여준다.

그림

7-15

깊이 우선 탐색의 결과인 비효율적 경로

7.6

다익스트라 알고리즘

네덜란드 과학자인 에츠허르 다익스트라

Edsger

Dijkstra

는 컴퓨터 과학 분야의 지적인 설립자