최단경로

최단경로 알고리즘 (Shortest Path)

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로 탐색 알고리즘

대표 두가지:

1. 플로이드 와샬 알고리즘 - 모든 노드를 방문하는 최단 경로
2. 다익스트라 알고리즘 - 특정 노드에서 다른 노드까지의 최단 경로

플로이드 와샬 (Floyd-Warshall) 알고리즘

1. 비용 배열, 방문 배열 선언
2. 시작점으로 설정
3. 방문하지 않은 노드가 있다면
4. 노드 완전탐색으로 비용배열의 거리 값 최소화
5. 방문하지 않은 노드 중 최소 비용 노드 위치 탐색
6. 해당 노드 방문 여부 체크

values = [2**31-1 for i in range(n)]
visited = [False for i in range(n)]
start = 0
visited[start]=True
values[start]=0
while False in visited:
		for i in costs:

다익스트라 (Dijkstra) 알고리즘

1. 비용 배열, 방문 배열 선언
2. 출발점 설정
3. 방문하지 않은 노드가 있다면
4. 방문하지 않은 지역 중 최솟값 찾기
5. 검사할 후보가 없다면 루프 탈출
6. 경로 완전탐색으로 비용배열 수정

visited = [False for _ in range(n)]
cost = [sys.maxsize for _ in range(n)[
visited[0] = True
cost[0] = 0
length = len(visited)
while Flase in visited:
	checkLoc = -1
	checkValue = sys.maxsize
	for i in range(length):
		if visited[i]==False and cost[i] < checkValue:
			checkLoc = i
			checkValue = cost[i]
		if checkLoc == -1:
			break
		visited[checkLoc] = True
		for v1, v2, c in costs:
			if v1 == chekckLoc and visited[v2] == False:
				cost[v2] = min(cost[v2], cost[v1]+c)
			if v2 == checkLoc and visited[v1[ == False:
				cost[v1] = min(cost[v1], cost[v2]+c)