최단경로 알고리즘 질문

[33(36.38)]

다익스트라 알고리즘 구현할려하는데 2차원배열로 각정점간의 길이를 저장하고 1차원배열에 시작점에서 도착점간의 최단거리를 저장하는 형식으로 할려하는데 이러면 최단거리는 구할수잇는데 경로를 못구함. 어떻게 해야할까요?

[배우고싶다(dbs1992)]

[익명(218.54)]

어느 경로가 가장 짧은지 저장해

[323(203.250)]

path 1차원 배열 만드셈. path[i]는 시작정점 v에서 i번째 정점으로의 최단 경로중 i직전에 나오는 정점을 저장하고 있으면 됨. 그리고 printPath 함수를 만드셈.

[33(36.38)]

그방법대로면 1->5로가는 최단거리를 가진 경로가 1->3->5라고 가정하면 5직전에 정점이 3이아니라 4일수도있잖음

[익명(218.54)]

1-5의 최단경로가 1-3-5면 5 직전의 정점이 3이잖아 뭔 소리임

[33(36.38)]

아니 예로들어줄게 4->5 까지의 가중치가 1이고 3->5까지의 가중치가 2이면 5직전의 정점은 4일텐데 4직전의 정점이 존재하지않는경우도 있고 여러 경우가많음 무조건 직전과 최단경로라고 도출되는게아님

[G(110.12)]

4직전의 정점이 존재하지 않으면 4는 출발지 정점이란 말이자나. 그러면 상관없지.

[이슬이(175.223)]

군대나가라

[33(36.38)]

군필요

[櫻木真乃(surgamidentidem)]

p[] array를 하나 주고 새 경로(즉 더 짧은 경로)를 찾을 때마다 p[해당도착점] = 직전 출발점 넣으면 되지 않음?

[櫻木真乃(surgamidentidem)]

초기값은 -1로 두고 p[최종도착점] = 최종도착점 바로 전의 위치 p[최종도착점 바로 전의 위치] = 그 이전의 위치 ... (계속 반복) 하면서 -1 나올때까지 인덱스 출력하면 그게 경로 아닐까

[櫻木真乃(surgamidentidem)]

쓰고나니까 위에 323 유동이랑 같은 말인거 같은데

[33(36.38)]

위에랑같은뜻이면 내가 적은내용이유 대로 안되지않음? 아니면 내가 너네말을 잘못이해한건가

[liliilli(125.188)]

각 노트 인덱스에 대해서 parent 에 대한 노드의 인덱스를 저장하는 toParentIdList[] 배열 같은걸 만들면 되잖음.

[櫻木真乃(surgamidentidem)]

http://gall.dcinside.com/board/view/?id=programming&no=936566&page=1