Нахождение кратчайшего расстояния между любыми двумя узлами в взвешенном графике - PullRequest
Новая
       37

Нахождение кратчайшего расстояния между любыми двумя узлами в взвешенном графике

0 голосов
/ 08 марта 2019

Итак, я хочу найти кратчайшее расстояние между любыми двумя узлами на этом графике, мне известны алгоритмы, необходимые для реализации этой идеи, но я не уверен, как мне это сделать.Я создал список смежности в виде ArrayList, который содержит startValue, EndValue и вес.Так, например: Banstead - это узел 1, он создается как объект: CreateNode (1,2,4), поэтому от Banstead до Coulsdon стоимость 4 между узлами 1 и 2.

GRAPH VISUALISED

вот код 

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

... и т. Д.

Как я могу реализовать алгоритм, который находит кратчайший путь между любыми двумя случайными узлами, скажем, Банстед и Хорли.Благодаря.

...