(알고리즘) 최단거리를 찾을 때(dijkstra) 해당 경로 출력하기

//previous[]을 두어 이전경로를 탐색 할 수 있게 끔 만들었다.
//이 알고리즘을 다익스트라를 이용했는데 주의 할점은 (순환이 되면안된다 또한 음수도 안된다)

public static void Get_It(int start,int dest)
{
int price[]=new int[N+1];
int previous[]=new int[N+1];


Arrays.fill(price,9999);

Stack<Node> stack=new Stack();

ArrayList<Edge> temp=nodes[start].e;

for(int next=0;next<temp.size();next++)
{
price[temp.get(next).to.from]=temp.get(next).distance;
stack.add(temp.get(next).to);
while(!stack.isEmpty())
{
Node S=stack.pop();
ArrayList<Edge> e=S.e;
for(int j=0;j<e.size();j++)
{
if(price[e.get(j).to.from]>price[S.from]+e.get(j).distance)
{
price[e.get(j).to.from]=price[S.from]+e.get(j).distance;
stack.add(e.get(j).to);
previous[e.get(j).to.from]=S.from;
}
}
}
}
for(int i=1;i<=N;i++)
System.out.println(previous[i]);

}

class Node
{
int from;
ArrayList<Edge> e;

Node(int from)
{
this.from=from;
e=new ArrayList<Edge>();
}
}
class Edge
{
Node from;
Node to;
int distance;
Edge(Node from,Node to)
{
this.from=from;
this.to=to;
this.distance=1;
}
}