未加权的最短路径

Question

如何找到具有最短加权路径的最短未加权路径...例如，如果我有两条未路径路径A-> B-> C = 2和A-> D-> F = 2。 ...我如何打印加权路径较小的那个？

的未加权和加权路径中的代码是这样的：

public void unweighted(String startName) 
{ 
    clearAll(); 

    Vertex start = vertexMap.get(startName); 
    if(start == null) 
     throw new NoSuchElementException("Start vertex not found"); 

    Queue<Vertex> q = new LinkedList<Vertex>(); 
    q.add(start); start.dist = 0; 

    while(!q.isEmpty()) 
    { 
     Vertex v = q.remove(); 

     for(Edge e : v.adj) 
     { 
      Vertex w = e.dest; 
      if(w.dist == INFINITY) 
      { 
       w.dist = v.dist + 1; 
       w.prev = v; 
       q.add(w); 
      } 
     } 
    } 
} 

加权：

public void dijkstra(String startName) 
{ 
    PriorityQueue<Path> pq = new PriorityQueue<Path>(); 

    Vertex start = vertexMap.get(startName); 
    if(start == null) 
     throw new NoSuchElementException("Start vertex not found"); 

    clearAll(); 
    pq.add(new Path(start, 0)); start.dist = 0; 

    int nodesSeen = 0; 
    while(!pq.isEmpty() && nodesSeen < vertexMap.size()) 
    { 
     Path vrec = pq.remove(); 
     Vertex v = vrec.dest; 
     if(v.scratch != 0) // already processed v 
      continue; 

     v.scratch = 1; 
     nodesSeen++; 

     for(Edge e : v.adj) 
     { 
      Vertex w = e.dest; 
      double cvw = e.cost; 

      if(cvw < 0) 
       throw new GraphException("Graph has negative edges"); 

      if(w.dist > v.dist + cvw) 
      { 
       w.dist = v.dist +cvw; 
       w.prev = v; 
       pq.add(new Path(w, w.dist)); 
      } 
     } 
    } 
} 

所以我想打印用更少的加权路径加权的路径，请帮助。

Answer 1

好的，我要对此进行粗略的刺探......循环查看未加权路径的列表。对于每一个，浏览路径结构，将所有权重相加。抓住价值最小的那个。您的代码将是这个样子，用一个典型的发现最大/最小模式：

int minimum = 99999; // use a value obviously larger than all paths 
PathClass minPath = null; 

for (PathClass path : unweightedPaths) { 
    int total = 0; 

    for (PathItemClass item : path) { 
     total += item.weight; 
    } 

    if (total < minimum) { 
     minimum = total; 
     minPath = path; 
    } 
} 

// do something with path, which is the smallest weighted path 

请让我知道，如果我在所有正确的轨道上？