我有一个用邻接矩阵表示的图,我想找出两个节点之间的最短路径。该图是加权的。我想使用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;
}
}所以基本上我的想法是找到两个给定节点之间的所有路径,并将它们存储在队列列表中,然后检查哪条路径具有最短的距离。你能帮帮我吗。
发布于 2014-03-28 19:08:58
有几种算法可以在您的案例中使用。一种非常常见的方法是使用Dijkstra算法:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
在google上搜索"Dijkstra's shortest path algorithm java“,会给出几个页面,其中包含如何在Java中实现的示例。
发布于 2014-03-28 19:13:06
Dijkstra的算法非常适合你的问题,这个网址是Link
https://stackoverflow.com/questions/22711110
复制相似问题