D[n][k]  (0<=k<=2)

시작점에서 n번 도시까지의 최단 경로는 min(D[n][k]) (0<=k<=2) 

n의 도시에 k개의 엣지를 바꿔서 온 최단 경로라고 구하면 될 거 같네요

sksdong1 댓글 감사합니다.

엣지의 갯수 말고 어떤 엣지를 바꿧는지에 대한 정보는 어떻게 고려되는건가요?

어떤 엣지를 바꿨는지의 정보는 필요없을 것 같은데,

만약 어떤 엣지를 바꿨는지를 기억하지 못하고 바꿨던 엣지를 또 바꾼다면 원래는 소비되지 않아야 할 비용이 그만큼 낭비되겠지만

그건 다른 데다 써도 될 바꾸기연산을 쓸데없이 허비한 거라 득이 안 되고, 따라서 다른 경로를 바꾼 더 좋은 경로가 반드시 있어서 그 답에 묻혀버릴것 같네요.

예를 들면 정점 u, v가 있을 때 u->v->u로 돌아오면서 경로를 2번 바꾸고 다음 정점 w로 이동하는 경로보다는

당연히 그냥 u에서 바로 w로 이동하는 게 더 짧은 경로를 만들 것이고... 따라서 경로 u->v->u는 묻혀버릴 겁니다.

아래와 같이 생각을 해봤는데요..

인접한 노드들에 대해서 min 값을 구한다면 계산 순서에 영향을 받을 것 같아서 안될 것 같습니다.

D[n][1] = min(D[n][0] + 1, D[n][1] + W, ... 모든 인접한 노드들에 대해서)

점화식으로 알려주실 수 있을까요? ㅠ.ㅠ

계산 순서를 다익스트라로 가중치 적은것부터 계산해 나가면 되지 않을까요