Discussion :

[choko83]

Bonjour,
Je voulais appliquer l'algorithme de Dijkstra (qui se trouve sur ce lien: http://algowiki.net/wiki/index.php/D...%27s_algorithm) pour le calcul du plus court chemin entre deux noeuds dans un graphe. Le problème que cet algorithme calcule tous les plus courts chemin entre le noeud source (premier noeud du graphe) et les autres noeuds. Mais, moi j'aimerai l'appliquer pour calculer le plus court chemin entre deux noeuds quelconques du graphe. Sachant que la classe java de l'agorithme est décrite ci-dessous, auriez-vous une idée comment modifier l'algorithme pour qu'on puisse calculer le plus court chemin entre deux noeuds quelconques?
Merci d'avance.

Voilà le code correspondant de l'algorithme de Dijkstra.

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
74
75
76
77
78
79
 
import java.util.*;
public class Dijkstra 
{
   // assumes Nodes are numbered 0, 1, ... n and that the source Node is 0
   ArrayList<Node> findShortestPath(Node[] nodes, Edge[] edges, Node target) 
   {
       int[][] Weight = initializeWeight(nodes, edges);
       int[] D = new int[nodes.length];
       Node[] P = new Node[nodes.length];
       ArrayList<Node> C = new ArrayList<Node>();
       // initialize:
       // (C)andidate set,
       // (D)yjkstra special path length, and
       // (P)revious Node along shortest path
       for(int i=0; i<nodes.length; i++)
       {
           C.add(nodes[i]);
           D[i] = Weight[0][i];
           if(D[i] != Integer.MAX_VALUE)
           {
               P[i] = nodes[0];
           }
       }
       // crawl the graph
       for(int i=0; i<nodes.length-1; i++)
       {
           // find the lightest Edge among the candidates
           int l = Integer.MAX_VALUE;
           Node n = nodes[0];
           for(Node j : C){
               if(D[j.name] < l)
               {
                   n = j;
                   l = D[j.name];
               }
           }
           C.remove(n);
           // see if any Edges from this Node yield a shorter path than from source->that Node
           for(int j=0; j<nodes.length-1; j++){
               if(D[n.name] != Integer.MAX_VALUE && Weight[n.name][j] != Integer.MAX_VALUE && D[n.name]+Weight[n.name][j] < D[j]){
                   // found one, update the path
                   D[j] = D[n.name] + Weight[n.name][j];
                   P[j] = n;
               }
           }
       }
       // we have our path. reuse C as the result list
       C.clear();
       int loc = target.name;
       C.add(target);
       // backtrack from the target by P(revious), adding to the result list
       while(P[loc] != nodes[0])
       {
           if(P[loc] == null)
           {
               // looks like there's no path from source to target
               return null;
           }
           C.add(0, P[loc]);
           loc = P[loc].name;
       }
       C.add(0, nodes[0]);
       return C;
   }
   private int[][] initializeWeight(Node[] nodes, Edge[] edges)
   {
       int[][] Weight = new int[nodes.length][nodes.length];
       for(int i=0; i<nodes.length; i++)
       {
           Arrays.fill(Weight[i], Integer.MAX_VALUE);
       }
       for(Edge e : edges)
       {
           Weight[e.from.name][e.to.name] = e.weight;
       }
       return Weight;
   }
}

[thelvin]

Oui. Pour deux nœuds quelconques a et b :

- Désigner a comme nœud source.
- Désigner b comme nœud destination.
- Appliquer l'algorithme de Dijkstra.

Hem... -_-°

[choko83]

Merci pour ta réponse.
J'ai pu enfin résoudre le problème en bricolant l'algorithme un peu .