Discussion :

[thasseda]

Bonjour,

Dans le code suivant, la méthode getShortestPathTo me retourne le chemin le plus court d'un graphe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }
}
 
/**Classe d'arc qu'on utilise dans la classe de Dijkstra**/
class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}
 
/**Classe de Dijkstra utilise pour le calcul du chemin le plus court**/
class Dijkstra
{
     // simple compute paths function
     public static void computePaths(Vertex source)
    {
        source.minDistance = 0.0;
        //Visit each vertex u, always visiting vertex with smallest minDistance first
        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.target;
                double weight = e.weight;
                //double distanceThroughU = u.minDistance + weight;
                double weight2=0;if (weight!=0){weight2=1;}    
                      //relax the edge (u,v)                
                        double distanceThroughU = u.minDistance + weight2;
 
        if (distanceThroughU < v.minDistance) {
        //remove v from queue
            vertexQueue.remove(v); 
 
            v.minDistance = distanceThroughU ; 
            v.previous = u;
             //re-add v to queue
            vertexQueue.add(v);
        }
            }
        }
    }
 
    //get shortest path function
    public static List<Vertex> getShortestPathTo(Vertex target)
    {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex node = target; node != null; node = node.previous)
            path.add(node);
 
        Collections.reverse(path);
        return path;
    }
}

Avec la fonction ci-dessous, je retourne le nombre d'arcs sur ce chemin le plus court:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public double getMinPath(){ 
    Vertex[] vv = new Vertex[nodes]; 
 
    String nom_noeud = new String();
    // we assign a number to each node i
    for (int i = 0 ; i <nodes; i++ ){
        nom_noeud =nom_noeud.valueOf(i);    
        vv[i] = new Vertex(nom_noeud);                                           
    }
    // Search edges neighbors of each node
    for (int i = 0 ; i <nodes; i++ ){
        int ii=neighbors[i].size();
        vv[i].adjacencies = new Edge[ii]; // adges neighbors of each node.
 
        Iterator it = neighbors[i].iterator();
        ii=0;
        while(it.hasNext()){
            Integer neighbor = (Integer)it.next();
            int n=neighbor.intValue();
            vv[i].adjacencies[ii++]=  new Edge(vv[n], arcCap[i][n]); // we save the neighbor edge with 
        }
    }
 
    Dijkstra.computePaths(vv[s]); // we call the Dijkstra class above to comput the minimal path with the starting node s.
 
    List<Vertex> path = Dijkstra.getShortestPathTo(vv[t]);
    System.out.println("  path : " + path);
 
    return vv[t].minDistance; // we return the number of edges of the minpath between s and t.
}

Quelqu'un saurait-il m'indiquer comment construire une fonction double qui me permette de retourner la probabilité du chemin le plus court, sachant qu'on attribue à chaque arc du graphe, une probabilité ?

Merci d'avance pour votre aide.

[wax78]

Bonjour,

Qu'entends tu par une fonction double ?

[thasseda]

Bonjour wax78,

La classe dijkstra me retourne le chemin le plus court d'un graphe "path".

Puis j'appelle cette classe dans la méthode public double getMinPath() qui me retourne la distance minimale entre un noeud et un autre, dans un graphe, ou plutôt le nombre d'arcs que le chemin le plus court contient.

A présent, j'aimerais modifier cela de manière à obtenir le chemin qui a le minimum d'arcs entre un noeud et un autre, en récupérant le chemin qui possède la plus grande probabilité, ainsi que la valeur de la probabilité.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Vertex implements Comparable<Vertex> {
 
    public final String    name;
    public Edge[]        adjacencies;
    public double        minDistance    = Double.POSITIVE_INFINITY;
    public Vertex        previous;
 
    public Vertex(String argName) {
 
        name = argName;
    }
 
    public String toString() {
 
        return name;
    }
 
    public int compareTo(Vertex other) {
 
        return Double.compare(minDistance, other.minDistance);
    }
}
 
/** Classe d'arc qu'on utilise dans la classe de Dijkstra **/
class Edge {
 
    public final Vertex    target;
    public final double    weight;
 
    public Edge(Vertex argTarget, double argWeight) {
 
        target = argTarget;
        weight = argWeight;
    }
}
 
/** Classe de Dijkstra utilise pour le calcul du chemin le plus court **/
class Dijkstra {
 
    // simple compute paths function
    public static void computePaths(Vertex source) {
 
        source.minDistance = 0.0;
        // Visit each vertex u, always visiting vertex with smallest minDistance first
        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.target;
                double weight = e.weight;
                // double distanceThroughU = u.minDistance + weight;
                double weight2 = 0;
                if (weight != 0) {
                    weight2 = 1;
                }
                // relax the edge (u,v)
                double distanceThroughU = u.minDistance + weight2;
                if (distanceThroughU < v.minDistance) {
                    // remove v from queue
                    vertexQueue.remove(v);
 
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    // re-add v to queue
                    vertexQueue.add(v);
                }
            }
        }
    }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
    public double getMinPath() {
 
        Vertex[] vv = new Vertex[nodes];
 
        String nom_noeud = new String();
        // we assign a number to each node i
        for (int i = 0; i < nodes; i++) {
            nom_noeud = nom_noeud.valueOf(i);
            vv[i] = new Vertex(nom_noeud);
        }
        // Search edges neighbors of each node
        for (int i = 0; i < nodes; i++) {
            int ii = neighbors[i].size();
            vv[i].adjacencies = new Edge[ii]; // adges neighbors of each node.
 
            Iterator it = neighbors[i].iterator();
            ii = 0;
            while (it.hasNext()) {
                Integer neighbor = (Integer) it.next();
                int n = neighbor.intValue();
                vv[i].adjacencies[ii++] = new Edge(vv[n], arcCap[i][n]); // we save the neighbor edge with
            }
        }
 
        Dijkstra.computePaths(vv[s]); // we call the Dijkstra class above to comput the minimal path with the starting node s.
 
        List<Vertex> path = Dijkstra.getShortestPathTo(vv[t]);
        System.out.println(" path : " + path);
 
        return vv[t].minDistance; // we return the number of edges of the minpath between s and t.
    }

[thasseda]

Bonjour tout le monde,

personne n'a une idée à mon problème, ou je ne suis pas dans la bonne rubrique!!!?