최단경로

플로이드 와샬 알고리즘

• 모든 노드를 방문하는 최단경로

# 전체적인 예시로써만 참고!
# 비용 배열
values=[2**31-1 for i in range(n)] # 문제에서 가져온 듯

# 방문 배열
visited =[False for i in range(n)]

# 0번 노드를 시작점으로 설정
start=0
visited[start]=True
values[start]=0

# 방문하지 않은 노드가 있다면
while False in visited:
	# 노드 완전 탐색으로 비용 및 배열의 거리 값 최소화
	for i in costs:#?? 이건 어디서 나왔지? 이것도 예시 각 노드별 비용으로 예상이됨
		if(visited[i[1]]==False and i[0]==start):
			values[i[1]]=min(values[i[1]],i[2])
		if(visited[i[0]]==False and i[1]==start):
			values[i[0]]=min(values[i[0]],i[2])
	refer=2**31-1 # 이것 또한
	# 방문하지 않은 노드 중 최소 비용 노드 위치 탐색
	for i in range(n):
		if(visited[i]==False and values[i]!=0):
			refer=min(refer,values[i])
	answer = answer + refer
	# 해당 노드 방문 여부 체크
	for i in range(n):
		if(visited[i]==False and values[i]==refer):
			visited[i]=True
			start=i
			break

다익스트라 알고리즘

• 특정 노드에서 다른 노드까지의 최단 경로

# 전체적인 예시로써만 참고!
# 비용 배열
cost=[sys.maxsize for _ in range(n)]

# 방문 배열
visited =[False for _ in range(n)]

# 0번 노드를 시작점으로 설정
visited[0]=True
cost[0]=0
length=len(visited)

# 방문하지 않은 노드가 있다면
while False 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==checkLoc 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)