أرجوا المساعدة أخوتي الاعزاء

اذهب الى الأسفل

أرجوا المساعدة أخوتي الاعزاء Empty أرجوا المساعدة أخوتي الاعزاء

مُساهمة من طرف taqwa35853 في الثلاثاء مايو 26, 2015 5:05 pm

السلام عليكم ورحمة الله وبركاته ...
أحتاج الى المساعدة في هدا الكود لDijkstra's algorithm .. أريد اضافة دالة لحساب اجمالي التكلفة أو اجمالي المسافة the total of shortest paths  

package dijestra4;

import java.util.PriorityQueue; // Q
import java.util.List; // list of Parent[0:n-1]
import java.util.ArrayList;    //Parent[0:n-1]
import java.util.Collections; // the path of   Nearest[v] 

class Vertex implements Comparable<Vertex>
{
public final String name;// call the name of vertix 
public Edge[] adjacencies; //    Dist[v] 
public double minDistance = Double.POSITIVE_INFINITY; // mindist[u]
public Vertex previous;            //Dist[u]
public Vertex(String vName) { name = vName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
    return Double.compare(minDistance, other.minDistance);
}
}
//class Cost{ 
// cost= v0.minDistance + v1.minDistance;
   
//}
class Edge
{
      // her we defined updating vertex and weigth 
public final Vertex v; //// // update Dist[v] and 
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ v = argTarget; weight = argWeight; }
}

public class Dijkstra1
{
public static void computePaths(Vertex source)
{
    source.minDistance = 0.;
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
    Vertex u = vertexQueue.poll();

        // Visit each edge exiting u
        for (Edge e : u.adjacencies)
        {
            Vertex v = e.v;
            double weight = e.weight;
            double distanceThroughU = u.minDistance + weight;
    if (distanceThroughU < v.minDistance) { // if dist[u] ? w(uv) < Dist[v] then 

        vertexQueue.remove(v);
        v.minDistance = distanceThroughU ;
        v.previous = u;
        vertexQueue.add(v);
    }
        }
    }
}
//her update Parent[v] and Dist[v] for those vertices v that are adjacent to u 
public static List<Vertex> getShortestPathTo(Vertex target)
{
    List<Vertex> path = new ArrayList<Vertex>();
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);
    Collections.reverse(path);
    return path;
}
//her we have the matrex of vertex and weigth
public static void main(String[] args)
{
   
//the matrex of vertex
Vertex v0 = new Vertex("A");
Vertex v1 = new Vertex("B");
Vertex v2 = new Vertex("C");
Vertex v3 = new Vertex("D");
Vertex v4 = new Vertex("E");
Vertex v5 = new Vertex("F");

//the matrix weight of edges
v0.adjacencies = new Edge[]{ new Edge(v1, Cool,
                             new Edge(v2, 5),
                             new Edge(v3, 6) };
v1.adjacencies = new Edge[]{ new Edge(v0, Cool,
                             new Edge(v2, 7),
                             new Edge(v4, 10) };
v2.adjacencies = new Edge[]{ new Edge(v0, 5),
                             new Edge(v1, 7) };
v3.adjacencies = new Edge[]{ new Edge(v0, 6),
                             new Edge(v4, 12) };
v4.adjacencies = new Edge[]{ new Edge(v1, 10),
                             new Edge(v3, 12) };

Vertex[] vertices = { v0, v1, v2, v3, v4 };
    computePaths(v0);
    for (Vertex v : vertices)
{
    //cost[] vertices = { v0, v1, v2, v3, v4 };
   // computePaths(v);
    
    System.out.println("ShortestPath from  A to the node  " + v + ": " + v.minDistance);
    List<Vertex> path = getShortestPathTo(v);
    System.out.println("Path: " + path);
    
    
}
}
}
وهذه هي مخرجات الكود 
ShortestPath from  A to the node  A: 0.0
[Path: [A
ShortestPath from  A to the node  B: 8.0
[Path: [A, B
ShortestPath from  A to the node  C: 5.0
[Path: [A, C
ShortestPath from  A to the node  D: 6.0
[Path: [A, D
ShortestPath from  A to the node  E: 18.0
[Path: [A, D, E

احتاج اضافة دالة total shortest paths  الى البرنامج بحيث تعطي التكلفة الاجمالية :0+8+5+6+18=37

ولكم مني جزيل الشكر 
taqwa35853
taqwa35853
.
.

تاريخ التسجيل : 15/03/2015
المساهمات : 7
النقاط : 11
التقيم : 0
الدولة : السعودية
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

أرجوا المساعدة أخوتي الاعزاء Empty رد: أرجوا المساعدة أخوتي الاعزاء

مُساهمة من طرف NEXT في الثلاثاء مايو 26, 2015 10:26 pm

يمكنك مراجعة المثال التالى :

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]

ـــــــــــــــــــ التوقيع ــــــــــــــــــــ
أرجوا المساعدة أخوتي الاعزاء Do.php?imgf=154090993464951
NEXT
NEXT
الادارة
الادارة

تاريخ التسجيل : 18/02/2011
المساهمات : 379
النقاط : 200555
التقيم : 14
الدولة : مصر
الجنس : ذكر

الرجوع الى أعلى الصفحة اذهب الى الأسفل

أرجوا المساعدة أخوتي الاعزاء Empty رد: أرجوا المساعدة أخوتي الاعزاء

مُساهمة من طرف taqwa35853 في الأربعاء مايو 27, 2015 7:40 am

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط] كتب:يمكنك مراجعة المثال التالى :

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]
شكرا جزيلا لك أخي الفاضل وجعله في مسزان حسناتك ...

لكن لاسف لم اتحصل على النتيجة المطلوبة ..
أولا لان البرنامج لم ينفد معي وايضا لاني لم اتمكن من اضافة دالة  Total Shortest path  الى برنامجي    وذلك لآن خبرتي ليست كبيرة بلغة الجافا .

شكرا ....
taqwa35853
taqwa35853
.
.

تاريخ التسجيل : 15/03/2015
المساهمات : 7
النقاط : 11
التقيم : 0
الدولة : السعودية
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

أرجوا المساعدة أخوتي الاعزاء Empty رد: أرجوا المساعدة أخوتي الاعزاء

مُساهمة من طرف taqwa35853 في الأربعاء مايو 27, 2015 8:05 am

السلام عليكم اخوتي ..
في الرنامج السابق حاولت البحث عن نفس الخوارزمية التالية ولكن لم استطع فهم البرنتمج جيدا ولذلك لخبرتي القليلة و لانه لا يحتوي على دالة Total Shortest path ..


فلو سمحتم اخوتي الاعزاء لو امكن كتابة برنامج بلغة الجافا بنفس كفية الخوارزمية التالية  وهي لDijkstra's algorithm .... والمطلوب قائمة من أقصر الطرق: العقد والتكلفة الإجمالية (listing of the shortest path: nodes and total cost)


 procedure Dijkstra(G, w, r, Parent[0:n-1], Dist)
        for v← 0 to n-1 do
          Dist[v] ← ∞
          InTheTree[v] ← .false.
         endfor
         Parent[r] ←-1
         Dist[r] ←0
         for Stage ←1 to n-1 do
          Select vertex u that minimises Dist[u] over all u such that InTheTree[u] = .false.
          InTheTree[u] = .true.                                       // add u to T
          for each vertex v such that uv E do             // update Dist[v] and
                          if .not. InTheTree[v]  then                // Parent[v] arrays
                          if Dist[u] ← w(uv) < Dist[v] then
                                   Dist[v] = Dist[u] + w(uv)
                                   Nearest[v] ←
taqwa35853
taqwa35853
.
.

تاريخ التسجيل : 15/03/2015
المساهمات : 7
النقاط : 11
التقيم : 0
الدولة : السعودية
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

أرجوا المساعدة أخوتي الاعزاء Empty رد: أرجوا المساعدة أخوتي الاعزاء

مُساهمة من طرف taqwa35853 في الأربعاء مايو 27, 2015 8:10 am

procedure Dijkstra(G, w, r, Parent[0:n-1], Dist)
        for v← 0 to n-1 do
          Dist[v] ← ∞
          InTheTree[v] ← .false.
         endfor
         Parent[r] ←-1
         Dist[r] ←0
         for Stage ←1 to n-1 do
          Select vertex u that minimises Dist[u] over all u such that InTheTree[u] = .false.
          InTheTree[u] = .true.                                       // add u to T
          for each vertex v such that uv ∈ E do             // update Dist[v] and
                          if .not. InTheTree[v]  then                // Parent[v] arrays
                          if Dist[u] ← w(uv) < Dist[v] then
                                   Dist[v] = Dist[u] + w(uv)
                                   (Nearest[v] ←w(uv)
                                   Parent[r] ← u
                          endif
                         endif
          endfor
        endfor

end Dijkstra
taqwa35853
taqwa35853
.
.

تاريخ التسجيل : 15/03/2015
المساهمات : 7
النقاط : 11
التقيم : 0
الدولة : السعودية
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

الرجوع الى أعلى الصفحة

ََ

مواضيع ذات صلة


 
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى