다익스트라 알고리즘

다익스트라 알고리즘

1. 너비우선탐색 vs 다익스트라 알고리즘

이전 포스트에서 김포공항에서 마포대교까지 가는 가장 빠른길이 아닌 가장 짧은길, 즉 최단경로를 구했다.

가장 적은 수의 구간을 지나긴 하지만 구간을 지날때마다 시간을 측정해보면 더 빠른 경로가 있을 수 있다.

가장 빠른경로를 찾고 싶다면 어떻게 해야 할까?

다익스트라 알고리즘을 사용하면 최단시간 경로를 구할 수 있다.

다익스트라 알고리즘을 사용해서 출발점에서 도착점으로 가는 가장 최단시간 경로를 구해보겠다.

다익스트라 알고리즘의 4단계

1. 가장 가격이 싼 정점을 찾는다. 가장 가격이 싼 정점은 도달하는데 시간이 가장 적게 걸리는 정점을 말한다.

2. 이 정점의 이웃정점들의 가격을 조사한다. 

이 정점의 이웃정점에 대해 현재의 가격보다 더 싼 경로가 존재하는지 확인한다. 만약 존재하면 가격을 수정한다.

3. 그래프 상의 모든 정점에 대해 이러한 일을 반복한다.

4. 최종경로를 계산한다.

정점 B의 모든 이웃 정점에 대해 정점 B를 통과하여 정점 A에 도달하는데 걸리는 시간 계산한다.

정점 A로 가는 더 짧은 거리 (6분에서 5분으로 수정)

도착점까지 가는 더 짧은 거리 (무한대에서 7분으로 수정)

정점 B에 도달하는데 2분 걸린다.

정점 A에 도달하는데 5분 걸린다.

도착점에 도달하는데 6분 걸린다.

그래프의 각 간선은 어떤 숫자값을 가지는데 이 숫자를 가중치라고 한다.

가중치를 가지는 그래프를 가중그래프(weighted graph)

가중치가 없는 그래프를 균일그래프(unweighted graph) 라고 한다.

다익스트라 알고리즘은 방향성 비순환그래프 또는 사이클을 가진경우 가중치가 양수일때만 적용된다.

3개의 해시테이블을 사용해 구현하기

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
 
print (graph["start"].keys())
print (graph["start"]["a"])
print (graph["start"]["b"])
 
'''
dict_keys(['a', 'b'])
6
2
'''
 
graph["a"]= {}
graph["a"]["fin"] = 1
 
graph["b"]= {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
 
graph["fin"]= {}
 
 
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
 
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
 
print (costs)
 
'''
{'a': 6, 'b': 2, 'fin': inf}
'''
 
processed = []
 
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node
 
node = find_lowest_cost_node(costs) #아직처리하지않은 가장 싼정점찾기
while node is not None: #모든 정점을 처리하면 반복문이 종료됨
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys(): # 모든이웃에 대해 반복함
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: #만약 이 정점을 지나는 것이 가격이 더 싸다면
            costs[n] = new_cost # 정점의 가격을 갱신하고
            parents[n] = node #부모를 이 정점으로 새로 설정합니다.
    processed.append(node) #정점을 처리한 사실을 기록합니다
    node = find_lowest_cost_node(costs) #다음으로 처리할 정점을 찾아 반복
 
print (processed)
 
'''
['b', 'a', 'fin']
'''

graph.pptx

dikstra_graph.py