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.