Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.paveloleynik.shortroute;
- import com.google.android.gms.maps.model.LatLng;
- import java.util.ArrayList;
- import java.util.List;
- /**
- * DijkstraAlgorithm
- * Created by MATHAHAKAR (Oleynik Pavel) on 25.02.2017.
- * Project: ShortRoute
- */
- public class WarshallAlgorithm {
- private static final WarshallAlgorithm D_A = new WarshallAlgorithm();
- private static List<LatLng> mPoints = new ArrayList<>();
- private static List<LatLng> fPoints = new ArrayList<>(); // for output
- public static List<LatLng> getRoute (List<LatLng> points) {
- mPoints.clear();
- fPoints.clear();
- addPoints(points);
- findRoute();
- return fPoints;
- }
- private static void addPoints (List<LatLng> points) {
- mPoints = points;
- }
- private static void findRoute () {
- while (mPoints.size() > 0) {
- double dist[] = new double[mPoints.size()];
- for (int j = 0; j < mPoints.size(); j ++) {
- if (j != 0) {
- dist[j] = getWeight(mPoints.get(0), mPoints.get(j));
- }
- }
- double min = findMinValue(dist);
- int iMin = 0;
- for (int m = 0; m < dist.length; m ++) {
- if (dist[m] == min) iMin = m;
- }
- fPoints.add(mPoints.get(iMin));
- mPoints.remove(0);
- if (mPoints.size() > 0) {
- for (int i = 1; i < mPoints.size(); i ++) {
- if (mPoints.get(i) != null) {
- LatLng latLng = mPoints.remove(i);
- mPoints.add(i - 1, latLng);
- }
- }
- }
- }
- }
- private static double findMinValue (double[] d) {
- double min = d[0];
- double max = min;
- for (int i = 0; i < d.length; i ++) {
- if (d[i] > max) max = d[i];
- if (d[i] < min) min = d[i];
- }
- return min;
- }
- private static double getWeight (LatLng latLng1, LatLng latLng2) {
- double ax = latLng1.latitude;
- double ay = latLng1.longitude;
- double bx = latLng2.latitude;
- double by = latLng2.longitude;
- return Math.sqrt( (Math.pow((bx - ax), 2)) + (Math.pow((by - ay), 2)) );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement