두 노드 사이의 최단 경로 찾기 더 이상 아이디어가 없습니다

보조 매트릭스로 표시된 그래프가 있는데 두 노드 사이의 최단 경로를 찾고 싶습니다. 그래프에 가중치가 적용됩니다. 나는 BFS 알고리즘을 사용하고 싶었지만 시도했지만 아이디어가 부족했다. 당신이 저를 도울 수 있다면 제 코드가 있습니다.두 노드 사이의 최단 경로 찾기 더 이상 아이디어가 없습니다

public class A { 
    private static int[][] adjacency = new int [4][4]; 
    static int n = 4; 

    public static void main(String[] args) { 
     for (int i=0;i<n;i++) 
      for (int j=0;j<n;j++) 
       adjacency[i][j] = 0;  
     adjacency[0][1] = 2; 
     adjacency[0][3] = 1; 
     adjacency[1][0] = 2; 
     adjacency[1][2] = 5; 
     adjacency[2][1] = 5; 
     adjacency[2][3] = 1; 
     adjacency[2][4] = 2; 
     adjacency[3][0] = 1; 
     adjacency[3][2] = 1; 
     adjacency[4][2] = 2; 
    } 

    public List<Integer> getNeighbors(int node, int[][] a) { 
     List<Integer> list = new ArrayList<Integer>(); 
     for(int i=0;i<n;i++) 
      if (a[node][i] != 0) 
       list.add(i); 
     return list; 
    } 

    public List<Queue<Integer>> findPath(int start, int end, int[][] a) { 
     List<Queue<Integer>> paths = new ArrayList<Queue<Integer>>(); 
     Queue<Integer> toVisit = new LinkedList<Integer>(); 
     Queue<Integer> visited = new LinkedList<Integer>(); 
     toVisit.add(start); 
     while(!toVisit.isEmpty()) { 
       int node = toVisit.remove(); 
       visited.add(node); 
       List<Integer> neighbors = new ArrayList<Integer>(); 
       neighbors = this.getNeighbors(node,a); 
     } 
      return paths; 
    } 
}

그래서 기본적으로 내가 무슨 생각 2 개 주어진 노드 사이의 모든 경로를 찾아 큐 목록에 저장 한 다음 최단 거리가되는 경로를 확인하는 것이 었습니다. 저를 도와주세요.

출처

2014-03-28 user3421241

BFS는 모든 링크에 걸쳐 동일한 무게의 최단 경로 알고리즘은 모든 링크는 같은 무게이다,이다? – Alejandro

http://en.wikipedia.org/wiki/Shortest_path_problem 읽으셨습니까? 나는 Dijkstra와 A *가 약간 비효율적이긴하지만 꽤 효과적이라는 것을 기억합니다. –

@ RB-Develop, 나는 그들이 최단 경로를 찾는 데 "비효율적"이라고 생각하지 않는다고 생각합니다. BFS를 Dijkstra/A *와 비교하는 경우 사과에 사과가 아닙니다. – Alejandro

귀하의 경우에 사용할 수있는 몇 가지 알고리즘이 있습니다. 가장 일반적인 방법은 Dijkstra의 알고리즘을 사용하는 것입니다. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

"Dijkstra의 최단 경로 알고리즘 java"는 Google에서 구현하는 방법에 대한 예제가있는 여러 페이지를 제공합니다.

출처

2014-03-28 11:08:57

좋은 대답입니다. Dijkstra가 A * 알고리즘의 특별한 경우라고 언급하는 것이 도움이 될 것이라고 생각합니다. – Alejandro

나는 Dijkstra가 더 좋을 것이라고 알고 있지만 BFS를 사용해야합니다. 그것은 필요합니다 – user3421241

@ user3421241 Dijkstra 's는 BFS의 한 유형입니다, 또한 A *는 BFS의 한 유형입니다. –

다 익스트라의 알고리즘이 문제에 이상적입니다, 이 URL은 Link

출처

2014-03-28 11:13:06 TechGuy

두 노드 사이의 최단 경로 찾기 더 이상 아이디어가 없습니다

답변

관련 문제