최단 경로 링크드리스트

Question

가장자리/경로 당 비용이 포함 된 유향 그래프를 나타내는 링크 된 목록의 목록에서 최단 경로를 찾고 싶습니다.

다음과 같이 보일 것이다 출력, 그것은 나에게이 정점 0에서 다른 정점에 도착하는 날을 것입니다 비용을 알려줍니다

d[0 to 0] = 0 
d[0 to 1] = 20 
d[0 to 2] = 10 

이것은 내가 내 목록을 채우는 방법입니다 테스트. 내 문제에 대한 지금

int vertex, int edgeCost; 

: 나는 모든 다른 사람의 정점 V에서 최단 경로를 찾으려면

LinkedList<GraphData> g = new LinkedList[3]; 

for (int i = 0; i < 3; i++) 
    weight[i] = new LinkedList<GraphData>(); 

g[0].add(new GraphData(1, 20); 
g[0].add(new GraphData(2, 10); 

GraphData 클래스는 다음과 같이 보인다.

public static int[] shortestPaths(int v, LinkedList<GraphData>[] cost) 
{ 
    // get the set of vertices 
    int n = cost.length; 

    // dist[i] is the distance from v to i 
    int[] dist = new int[n]; 

    // s[i] is true if there is a path from v to i 
    boolean[] s = new boolean[n]; 

    // initialize dist 
    for(int i = 0; i < n; i++) 
     dist[i] = cost[v].get(i).getCost(); 

    s[v] = true; 

    // determine n-1 paths from v 
    for (int j = 2 ; j < n ; j++) 
    { 
     // choose u such that dist[u] is minimal for all w with s[w] = false 
     // and dist[u] < INFINITY 
     int u = -1; 

     for (int k = 0; k < n; k++) 
      if (!s[k] && dist[k] < INFINITY) 
       // check if u needs updating 
       if (u < 0 || dist[k] < dist[u]) 
        u = k; 
     if (u < 0) 
      break; 

     // set s[u] to true and update the distances 
     s[u]=true; 

     for (int k = 0; k < n; k++) 
      if (!s[k] && cost[u].get(k).getCost() < INFINITY) 
       if(dist[k] > dist[u] + cost[u].get(k).getCost()) 
        dist[k] = dist[u] + cost[u].get(k).getCost(); 

     // at this point dist[k] is the smallest cost path from 
     // v to k of length j. 
    }  
    return dist; 
} 

이 줄 dist [i] = cost [v] .get (i) .getCost(); "IndexOutOfBoundsException"을 던졌습니다.

내가 뭘 잘못하고 있는지 알겠습니까? 어떤 도움을 주시면 감사하겠습니다.

Answer 1

아마도 cost[v].get(i) 요소가 없습니다 (이 의 색인 i은 cost[v]입니다). 인접리스트와 인접 행렬 :

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html#get(int)

Answer 2

그래프를 대표하는 일반적인 두 가지 방법이 있습니다.

인접 목록 : 목록 배열. 인덱스 i의 요소는 정점 i의 나가는 모서리를 포함하는 작은 목록입니다. 이것은 목록을 채울 때 작성하는 것입니다.

인접 행렬 : cost[i][j]가 j 버텍스 정점 i에서 에지의 비용을 포함하는 배열로 어레이. 인접 매트릭스 인 것처럼 cost 매개 변수를 사용 중입니다.

당신은 두 가지 옵션이 있습니다

• 변경 배열의 배열
• 변경하는 대신 인접 행렬의 인접리스트로 cost을 치료하는 알고리즘을 인접성 매트릭스를 생성하고 사용하는 그래프 구조를

다음은 두 번째 옵션입니다. 몇 가지 이름을 변경하고 초기화를 단순화하여 첫 번째 반복에서 인접한 사람의 거리를 v으로 계산합니다 (처음에는 특수한 경우와 달리).

import java.util.*; 

public class Main 
{ 
    public static int[] shortestPaths(int v, LinkedList<Edge>[] edges) 
    { 
     // get the set of vertices 
     int n = edges.length; 

     // dist[i] is the distance from v to i 
     int[] dist = new int[n]; 
     for (int i = 0; i < n; i++) { 
      dist[i] = Integer.MAX_VALUE; 
     } 

     // seen[i] is true if there is a path from v to i 
     boolean[] seen = new boolean[n]; 

     dist[v] = 0; 

     // determine n-1 paths from v 
     for (int j = 0; j < n; j++) { 
      // choose closest unseen vertex 
      int u = -1; 

      for (int k = 0; k < n; k++) { 
       if (!seen[k]) { 
        // check if u needs updating 
        if (u < 0 || dist[k] < dist[u]) { 
         u = k; 
        } 
       } 
      } 

      if (u < 0 || dist[u] == Integer.MAX_VALUE) { 
       break; 
      } 

      // at this point dist[u] is the cost of the 
      // shortest path from v to u 

      // set seen[u] to true and update the distances 
      seen[u] = true; 

      for (Edge e : edges[u]) { 
       int nbr = e.getTarget(); 
       int altDist = dist[u] + e.getCost(); 
       dist[nbr] = Math.min(dist[nbr], altDist); 
      } 
     } 

     return dist; 
    } 

    public static void main(String[] args) 
    { 
     int n = 5; 
     int start = 0; 
     LinkedList<Edge>[] cost = new LinkedList[n]; 
     for (int i = 0; i < n; i++) { 
      cost[i] = new LinkedList<Edge>(); 
     } 

     cost[0].add(new Edge(1, 20)); 
     cost[0].add(new Edge(2, 10)); 
     cost[1].add(new Edge(3, 5)); 
     cost[2].add(new Edge(1, 6)); 

     int[] d = shortestPaths(start, cost); 
     for (int i = 0; i < n; i++) { 
      System.out.print("d[" + start + " to " + i + "] = "); 
      System.out.println(d[i]); 
     } 
    } 
} 

class Edge 
{ 
    int target, cost; 

    public Edge(int target, int cost) { 
     this.target = target; 
     this.cost = cost; 
    } 

    public int getTarget() { 
     return target; 
    } 

    public int getCost() { 
     return cost; 
    } 
} 

Answer 3

문제는 색인이 일치하지 않는다는 것입니다.당신은 단지 예를

cost[0].add(new GraphData(5, 20)); 

에 대해 하나 개의 거리를 넣을 경우 20을 얻기 위해

cost[0].get(0).getCost(); 

을해야하기 때문에 다음

cost[0].get(5).getCost(); 

은 매우 혼란이다 (IndexOutOfBoundsException가 발생합니다).

가장자리 비용을 인코딩하려면 List 대신 Map을 사용하는 것이 좋습니다.

당신은 Map이와

List<Map<Integer, Integer>> g = new ArrayList<>(); 

for (int i = 0; i < 3; i++) 
    g.add(new HashMap<Integer, Integer>()); 

g.get(0).put(1, 20); 
g.get(0).put(2, 10); 

처럼, 당신은 아마도

// initialize dist 
for(int i = 0; i < n; i++) 
    dist[i] = cost.get(v).containsKey(i) ? cost.get(v).get(i) : INFINITY;