calculate shortest distance between cities

كيف تسجل المسافات بين المدن بدون Graph ؟ 

اهلا اختي, اذكر قبل مده طويله صادقتني مشكله في حساب بعد اللاعبين عن بعضهم البعض على قراف في لعبه بسيطه بالبايثون. بالنسبه لك اعتقد تحتاجي فهم اكبر للمشكله قبل البحث عن حل لها. اطلعي على هذه المقاله Distance between two points. وبقية الروابط التاليه, الفهم هو نصف الحل:

كيف يمكن حساب اقصر مسافة للمدن

تحتاجي خوارزميات لهذا الشئ, اعتقد بوجود جائزة بملايين الدولارات اذا شخص ابتكر خوارزميه كفائتها عاليها للحساب بين اقصر المدن. توجد خوارزمية حالياً مشتقه من النحل 🐝 وتسمى بخوارزمية النحل.

 Bees algorithm

The only condition for the application of the bees algorithm is that some measure of distance between the solutions is defined.

بمعنى لنفترض عندي مدينة  a,b,c,d  وراندوملي راح ابدأ ب a ف  احسب المسافة  بين a&b ثم a&c ثم a&d واختار اقصر مسافة ولنفترض انها c

ثم ارجع احسب المسافة بين c و b&d واشوف الاقصر وهكذا.

صادفت هذا مقطع من قبل جميل يشرح خوارزميه بالضبظ للشئ الي تريد Algorithm Documentary, يبدء الشرح من الدقيقه العاشرة تقريباً.

فهل ممكن الجافا يسويها خصوصا ان المدن  بتكون في. arrayList وليس في قراف كما متعارف عليه.

بالتأكيد الجافا يسويها واي لغة اخرى الحل يكمن في خوارزميه لا لغة برمجة, هنا اغلب الخوارزميات بلغة الجافا: All Algorithms implemented in Java. ولكن مثل ماتفضل الاخ عمار مايصير نحسب شئ بدون احداثياته, لازم قراف او احداثيات المدن راح يكون فيه حلول متوفره بالانترنت كثيره.

import java.util.*;
import java.util.ArrayList; 
public class Shortestdistance {
   public static void main(String[] args) {
   
      Scanner scn = new Scanner(System.in);
      System.out.print("How many points are there?");
       int x=scn.nextInt();
      double ShortestDistances=0.0;
      Point [] points = new Point[x];      
      System.out.println("Enter each point as x y, followed by 'Enter'.");
      for(int i =0; i<points.length; i++)
      {
         points[i] = new Point(scn.nextDouble(), scn.nextDouble());
         scn.nextLine();
      }
       ArrayList<Double> dis = new ArrayList<Double>(x);
      dis =calculateShortestDistances(points);
      for(int i =0; i<dis.size(); i++){
         System.out.println("The shortest Distances is: "+dis.get(i));
      }
   
   }//end main
   public static ArrayList<Double> calculateShortestDistances(Point [] p) {// start method calculateShortestDistances
      double distance;
      ArrayList<Double> D = new ArrayList<Double>();
      ArrayList<Double> shortD = new ArrayList<Double>();
      Point temppo;
      for(int i=0; i<p.length; i++)    {//start for 
         for(int k=i+1; k<p.length; k++)    {//start inner for 
            distance= Math.sqrt(Math.pow(p[i].getX()-p[k].getX(),2)+Math.pow(p[i].getY()-p[k].getY(),2));
            D.add(distance);         
         }//end inner for
         shortD.add(Min(D));
       
}//end for
      return shortD;
   }
   public static double Min(ArrayList<Double> num){
      double minValue = num.get(0);
         for (int j = 1; j <num.size(); j++) {
            if (num.get(j) < minValue ) {
               minValue = num.get(j);
            }}
      return  minValue; }

}//end class

مثلاً زي هالكود البسيط مبدئياً راح يتم قراءة الإحداثيات كقيم من المستخدم مثلا اخترنا ٤ احداثيات ولتكن ٢ ١ ، ٩  ٦ ، ٥  ٧  ، ١٥ ٨

مفروض في كل مرة يجيب اقصر مسافة بالنسبة للاحداثي ٢ ١ ف. راح يحسب المسافة بين  هالاحداثي وكل القيم الاخرى ويخزنها الاراي ليست D ويجب اقصر مسافة بارسال  D لميثود المينيمم عشان تجيب اقصر مسافة وهكذا 

الحسابات تمام لكن فيه مشكلة ماعرف ايش هي بالنسبة لفكرة اقصرمسافة حيث انه يجب اول ثنتين فقط وما يكمل حساب