가중치가없는 최단 경로

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 

내가 올바른 방향에 있다면 알려주시겠습니까 ??