playdataAlgo shortestPath(최단경로)🚀

playdataAlgo shortestPath(최단경로)🚀

---

최단경로

• 플로이드 아샬 알고리즘- 모든 노드를 방문하는 최단 경로

• 다익스트라 알고리즘 - 특정 노드에서 다른 노드까지의 최단 경로

---

플로이드 와샬

✅0번에서 탐색

비용배열

0	1	2	3	4	5
0	7	maxsize	maxsize	3	10

방문배열

0	1	2	3	4	5
True	False	False	False	True	False

0에서 시작할 때 갈 수 있는 노드는 4번, 1번, 5번 노드이다. 여기서 이동할대 최소비용으로 이동할 수 있는 4번 노드를 선택한다.

✅4번에서 탐색

비용배열

0	1	2	3	4	5
0	7,2 -> 2	maxsize	11	3	10

방문배열

0	1	2	3	4	5
True	True	False	False	True	False

✅1번에서 탐색

비용배열

0	1	2	3	4	5
0	2	4	11,10->10	3	10,6->6

방문배열

0	1	2	3	4	5
True	True	True	False	True	False

✅2번에서 탐색

비용배열

0	1	2	3	4	5
0	2	4	10,2 -> 2	3	6

방문배열

0	1	2	3	4	5
True	True	True	True	True	False

✅3번에서 탐색

비용배열

0	1	2	3	4	5
0	2	4	2	3	6,9->6

방문배열

0	1	2	3	4	5
True	True	True	True	True	True

모든경로 비용 : 0+2+4+2+3+6=17

코드로 구현

values = [2**31-1 for i in range(n)]  
visited = [False for i in range(n)] //비용 배열 거리 선언
start = 0   // 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

다익스트라 알고리즘

✅0번에서 탐색

비용배열

0	1	2	3	4	5
0	7	maxsize	maxsize	3	10

방문배열

0	1	2	3	4	5
True	False	False	False	True	False

4번으로 이동할때 최소경로가 되므로 4번으로 이동해 탐색

✅4번에서 탐색

비용배열

0	1	2	3	4	5
0	7, 3+2 -> 5	maxsize	3+11->14	3	10

방문배열

0	1	2	3	4	5
True	False	False	False	True	False

1번으로 갈때 최소비용이 되므로 1번으로 이동하여 탐색

✅1번에서 탐색

비용배열

0	1	2	3	4	5
0	5	5+4 -> 9	14, 5+10->14	3	10, 5+6 ->10

방문배열

0	1	2	3	4	5
True	True	True	False	True	False

1번에서 이동할 수 있는 곳은 2, 3, 5
이중에서 2번이 최소이므로 2번으로 이동

✅2번에서 탐색

비용배열

0	1	2	3	4	5
0	5	9	14, 9+2 ->11	3	10, 5+6 ->10

방문배열

0	1	2	3	4	5
True	True	True	False	True	True

✅5번에서 탐색

비용배열

0	1	2	3	4	5
0	5	9	11, 10+9 ->11	3	10, 5+6 ->10

방문배열

0	1	2	3	4	5
True	True	True	True	True	True

3번까지 탐색해주면 알고리즘이 종료된다.

코드로 구현

visited = [False for _ in range(n)]

cost = [sys.maxsize for _ in range(n)]
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[v2] == False:
            cost[v1] = min(cost[v1], cost[v2] + c)