首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >寻找2个节点之间的最短路径没有更多的想法

寻找2个节点之间的最短路径没有更多的想法
EN

Stack Overflow用户
提问于 2014-03-28 19:06:10
回答 2查看 95关注 0票数 0

我有一个用邻接矩阵表示的图,我想找出两个节点之间的最短路径。该图是加权的。我想使用BFS算法,我已经尝试过了,但我没有想法了。这是我的代码,如果你能帮我的话。

代码语言:javascript
复制
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;
    }
}

所以基本上我的想法是找到两个给定节点之间的所有路径,并将它们存储在队列列表中,然后检查哪条路径具有最短的距离。你能帮帮我吗。

EN

回答 2

Stack Overflow用户

发布于 2014-03-28 19:08:58

有几种算法可以在您的案例中使用。一种非常常见的方法是使用Dijkstra算法:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

在google上搜索"Dijkstra's shortest path algorithm java“,会给出几个页面,其中包含如何在Java中实现的示例。

票数 3
EN

Stack Overflow用户

发布于 2014-03-28 19:13:06

Dijkstra的算法非常适合你的问题,这个网址是Link

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22711110

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档