0

所以我想找到这张图上任意两个节点之间的最短距离，我知道实现这个想法所需的算法，但我不确定我将如何去做。我将邻接列表创建为一个 ArrayList，其中包含一个 startValue、EndValue 和一个权重。例如： Banstead 是节点 1，它被创建为一个对象： CreateNode(1,2,4) 所以从 Banstead 到 Coulsdon 的成本是节点 1 和节点 2 之间的 4。

图表可视化

这是代码

package map;

import java.util.ArrayList;

 class Edge {
    int startVertex;
    int endVertex;
    int weight;
public Edge(int start, int end, int weight){
    this.startVertex = start;
    this.endVertex = end;
    this.weight = weight;
     }
}
public class Map {


public static void main(String[] args) {

    int vertex = 17;
    int[][] matrix = new int[vertex+1][vertex+1];

    ArrayList<Edge> edgeList = new ArrayList<Edge>();
    edgeList.add(new Edge(1,2,4));edgeList.add(new Edge(1,17,3));
    edgeList.add(new Edge(2,1,4));edgeList.add(new Edge(2,4,4));edgeList.add(new Edge(2,10,5));
    edgeList.add(new Edge(3,4,1));edgeList.add(new Edge(3,6,5));
    edgeList.add(new Edge(4,2,4));edgeList.add(new Edge(4,3,1));edgeList.add(new Edge(4,5,2));
    edgeList.add(new Edge(5,4,2));edgeList.add(new Edge(5,6,3));edgeList.add(new Edge(5,9,4));edgeList.add(new Edge(5,10,5));
    edgeList.add(new Edge(6,3,5));edgeList.add(new Edge(6,5,3));edgeList.add(new Edge(6,7,2));
    edgeList.add(new Edge(7,6,2));edgeList.add(new Edge(7,8,5));
    edgeList.add(new Edge(8,7,5));edgeList.add(new Edge(8,9,4));edgeList.add(new Edge(8,12,5));
    edgeList.add(new Edge(9,5,4));edgeList.add(new Edge(9,7,4));edgeList.add(new Edge(9,12,5));
    edgeList.add(new Edge(10,2,5));edgeList.add(new Edge(10,5,5));edgeList.add(new Edge(10,13,1));edgeList.add(new Edge(10,14,3));
    edgeList.add(new Edge(11,9,4));edgeList.add(new Edge(11,12,3));edgeList.add(new Edge(11,13,3));
    edgeList.add(new Edge(12,8,5));edgeList.add(new Edge(12,11,3));edgeList.add(new Edge(12,14,4));
    edgeList.add(new Edge(13,8,5));edgeList.add(new Edge(13,11,3));edgeList.add(new Edge(13,14,4));
    edgeList.add(new Edge(14,10,1));edgeList.add(new Edge(14,11,3));
    edgeList.add(new Edge(15,12,4));edgeList.add(new Edge(15,14,5));edgeList.add(new Edge(15,16,9));
    edgeList.add(new Edge(16,13,9));edgeList.add(new Edge(16,17,1));
    edgeList.add(new Edge(17,1,3));edgeList.add(new Edge(17,16,1));

    for(int i=0; i<edgeList.size(); i++){
    Edge currentEdge = edgeList.get(i);
    int startVertex = currentEdge.startVertex;
    int endVertex = currentEdge.endVertex;
    int weight = currentEdge.weight;
    matrix[startVertex][endVertex] = weight;
    }

    for(int i=1; i<=vertex; i++){
        for(int j=1; j<=vertex; j++){
            System.out.print(matrix[i][j]);
        }
        System.out.println();
    }
}

}

输出只是邻接列表的显示：

 04000000000000003
 40040000050000000
 00010500000000000
 04102000000000000
 00020300450000000
 00503020000000000
 00000205000000000
 00000050400500000

... 等等。

我如何实现一种算法来找到任意两个随机节点之间的最短路径，比如 Banstead 和 Horley。谢谢。

4

0 回答 0