java - Dijkstra - 定位上一个 vector

Question

这是我的类 Dijkstra 示例代码:

public class Dijkstra {

    public static int[] GetPath(IGraph graph,int start,int end){

    int[] dist=new int[graph.size()+1];
    Stack<Integer> Path =new Stack<Integer>();
    int[] previous=new int[graph.size()+1];
    boolean[] visited=new boolean[graph.size()+1];

    HashSet<Integer> Q=new HashSet<Integer>();

    int i,u = 0,min;

    for (i=0;i<graph.size();i++){
        dist[i]=10000;
        visited[i]=false;
        previous[i]=-1;     
    }
    dist[start]=0;  
    Q.add(start);

    while(!Q.isEmpty()){
        min=1000;   
        for(i=0;i<graph.size();i++){
            if(dist[i]<min&&visited[i]==false){
                min=dist[i];
                u=i;

            }
        }

        Q.remove(u);
        visited[u]=true;

        //Process all the outbound vertexes of the current vertex;
        int[] outb=graph.IterateOutbound(u);
        if(outb!=null){
            for (int v=0;v<outb.length-1;v++){
                int alt=dist[u]+graph.retrieveCost(u, outb[v]);
                if(alt<dist[outb[v]]&&!visited[outb[v]]){
                    dist[outb[v]]=alt;
                    previous[outb[v]]=u;
                    Q.add(outb[v]);

                }
            }
        }
    }
    return previous;
    }


}

我不知道如何使用“前一个” vector (其中保存了算法访问的每个顶点，直到它成功，但不是成本最低的那个)返回正确的路径 -成本较低的那个。当我用谷歌搜索时，我发现我需要另一个函数(使用“前一个” vector )来计算路径。或者有人有其他想法？ '

附加信息:Graph 是一个具有属性的类 - innies,outies,cost .. IterateOutbound 是一个函数，返回一个顶点的出站顶点列表 我从文件中读取信息

Answer 1

是的，您基本上需要多几行代码(您可以将其放入函数中)来计算到顶点的路径。

类似于:(伪代码)

Stack getPath(int[] previous, int start, int end)
   int current = end
   Stack path
   path.push(current)
   while (current != start)
      current = previous[current]
      path.push(current)
   return path

此算法的高级描述相当简单:

• 从头开始
• 重复查看前一个元素，直到我们到达开头，边走边存储顶点

为什么是堆栈？因为我们从路径的末尾压入元素，所以我们压入的最后一个元素是开始，如果使用 Stack，这将是我们弹出的第一个元素。