Salut, je dois faire une comparaison entre le temps d'execution de Dijkstra classqiue et Dijkstra avec Fibonacci. En fait, normalement Dijkstra avc les tas de Fibonacci donne une complexité O(m +n log n) et Dijkstra classique a une complexité de O (n²). Mon problème c'est que lors de l'execution, je trouve le contraire, et le temps d'execution de Dijkstra class est moins que celui avc Fibonacci..

le code de Dijkstra avec Fibonacci est le suivant:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
public void dijkstr(double[][] graph, int dest,FIB Q,Node nd[])throws IOException{
              int min,i=0;
           while(i<graph.length ){
               min=Q.removeMin().indice;// removeMin() sa comlexité est: O(log n)
              for( int j = 0; j < graph.length; j++ ){
                if( nd[j].m_key>graph[ min ][ j ] + nd[min].m_key ){
                Q.decreaseKey(nd[j], (int)graph[ min ][ j ] + nd[ min ].m_key); } }
                   i++;   //decreaseKey() sa complexité est : O(1)
                       }

le code de Dijkstra classique est:
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
public void dijkstr(double[][] graph, int dest ,Node nd[])throws IOException{
 
 
                int dC[] = new int[ graph.length  ];
 
                int p[] = new int[ graph.length  ];
 
                for( int i = 0; i < graph.length ; i++ )
                { 
                  dC[ i ] = 100; p[ i ] = -1; }
 
                 dC[ 0 ] = 0;
 
             int i = 0;    int min = 1000, pos = 0; 
 
                while( i<graph.length){
 
                        for( int j = 0; j < graph.length; j++ ){
 
                                if( min > nd[ j ].m_key && dC[ j ] != -1 ){
 
                                        min = nd[ j ].m_key; pos = j;   }  }
 
                        dC[ pos ] = -1; 
 
                        for( int j = 0; j < graph.length; j++ ){
                        if( nd[ j ].m_key > graph[ pos ][ j ] + nd[ pos ].m_key ){
 
                          nd[ j ].m_key = (int)graph[ pos ][ j ] + nd[ pos ].m_key;
 
                         p[ j ] = pos; }   }
 
                        i++; min = 1000;  }
Svp qui peut m'aider! merci d'avance