최단경로

최단경로를 풀 때 가장 먼저 등장하는것이 Dijkstra와 Floyd라고 생각된다.
다익스트라의경우 일반적으로 O(n^2)이지만, Heap구조를 사용하는 순간 O(NlogN)의 시간복잡도로 줄일 수 있으며,
플로이드의 경우 아주간단하게 빼박 O(n^3)이다.

먼저 다익스트라부터 본다면
graph를 만들어 놓고 시작하자.

나는 주로 파이썬의 딕셔너리를 활용해서 graph를 만들고 시작한다.

def mkgraph(ss):
    from collections import defaultdict
    dic=defaultdict(list)
    for fr,to,cost in ss:
        dic[fr].append([to,cost])
        dic[to]
    return dic
costs=[
    [1,2,2],[1,4,1],[1,3,5],[2,3,3],[2,4,2],[3,2,3],[3,6,5],[4,3,3],[4,5,1],[5,3,1],[5,6,2]
]
# dijkstra(mkgraph(costs),1)
mkgraph(costs)

이렇게 하는것이 한눈에 가독성도 좋다고 생각되기에.. 이렇게 한다..
양방향 그래프가 아닌경우 dic[to] 만을 통해서 node가 비어있지 않도록 한다. (순회 시 참조에서 Key가 없는 오류발생을 막기위함)
양방향이라면 dic[to].append([fr,cost]) 를 통해서 양방향으로 만들어준다.

일단 이렇게 그래프만드는것이 끝났으니, 이제 다익스트라를 구현해보자.

from heapq import *
def dijkstra(graph,start):
    INF = int(1e9)
    distances={i : INF for i in graph}
    frt={i:0 for i in graph}
    distances[start]=0
    frt[start]=start
    q = [[0,start]]
    while q:
        dist,now = heappop(q)
        if dist> distances[now]: continue
        for node,n_dist in graph[now]:
            new_dist = dist+n_dist
            if new_dist<distances[node]:
                distances[node] = new_dist
                frt[node] = now
                heappush(q, [new_dist,node])
    return distances, frt

def getRoute(frtable,st,fr):
    tmp=[]
    while st!=fr:
        tmp.append(fr)
        fr=frtable[fr]
    ans=[st,]
    while tmp:
        ans.append(tmp.pop())
    return ans

graph = mkgraph(costs)
dist, frtable = dijkstra(graph,1)
getRoute(frtable,1,5) # 1,4,5 

난 다익스트라를 쓸 때 이후 경로까지 확인할 수 있도록 frt (from table) 을 사용한다.
이를 통해 각각의 노드가 어디에서 온것인지 알 수 있으며, 그것을 역으로 따라올라간다면, start까지 찾아감으로써 경로를 찾을 수 있다.

여담으로 floyd또한 다익스트라보다 쉽게 구현할 수 있는데. , . .
여기서는 graph보다 matrix를 활용하는것이 더욱 좋다..
links의 입력 방식에 따라 매트릭스를 구성하는 것은 쉬우니..

def solution(links,start,mid,end):
    def mkmat(links):
        nodecnt=set()
        for fr,t in links:
            nodecnt.add(fr)
            nodecnt.add(t)
        mat=[[int(1e9)]*len(nodecnt) for _ in range(len(nodecnt))]
        for fr,to in links:
            mat[fr-1][to-1]=1
            mat[to-1][fr-1]=1
        for i in range(len(nodecnt)):
            mat[i][i]=0
        return mat
    def floyd(mat):
        for mid in range(len(mat)):
            for fr in range(len(mat)):
                for to in range(len(mat)):
                    mat[fr][to] = min(mat[fr][to], mat[fr][mid]+mat[mid][to])
        return mat

    mat=mkmat(links)
    mat = floyd(mat)
    print(mat)

    dist= mat[start-1][mid-1] + mat[mid-1][end-1]
    return dist if dist<int(1e9) else -1

링크만 주어진 상황으로 생각하고, 링크에 등장하지 않는 노드는 없다고 가정한다면, mkmat을 통해 링크테이블을 만들고,
플로이드를 통해 각 링크를 순회하며 연산을 진행
fr, mid, to를 사용하여 보기좋게 사용할 수 있다!