Discussion :

[Premium]

Bonjour,

je dois coder ces algos dans le cadre de mon projet.
Je sais bien que ces algos sont disponibles sur le web mais j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

Merci d'avance de votre aide

[FrancisSourd]

j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

La question est trop vaste. Une réponse courte c'est: "lis les livres" puisqu'une réponse longue consisterait à écrire un véritable livre...

Les algos fournis dans les cours ou dans les bouquins ont déjà une bonne complexité (la meilleure connue en général): si ton code a la même complexité que le code sur le papier c'est déjà que ton projet est bien ficelé.

Il y a eu récemment une discussion sur les améliorations possibles de Dijkstra mais je ne sais pas si c'est ce que tu cherches...
http://www.developpez.net/forums/viewtopic.php?t=417123

[BiLLKiLL]

d'après mes cours, les complexités sont de :

Prim : O(mLogn) avec un Tas comme SD pour trouver rapidement l'arc de poids minimum appartenant au cocycle.
Kruskal : O(max(mLogn,m+ nlog n)) avec une SD Union Find
Dijkstra : O(mLogn) avec un Tas
FloydWarshall : O(n^3)
Je ne connais pas Bellman-Ford, je ne connais que Bellman tout court (O(mn) avec une liste FiFo mais de toute façon il en existe tellement de version !)

[FrancisSourd]

Je ne connais pas Bellman-Ford, je ne connais que Bellman tout court (O(mn) avec une liste FiFo mais de toute façon il en existe tellement de version !)

En général, l'algo de Ford est l'adaptation de l'algo de Bellman dans le cas où il n'y a pas de circuit dans le graphe. Grâce à cette propriété, on est assuré que l'optimum est trouvé dès la première itération de Bellman, ce qui fait un algo en O(m).

[Premium]

j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

La question est trop vaste. Une réponse courte c'est: "lis les livres" puisqu'une réponse longue consisterait à écrire un véritable livre...

Les algos fournis dans les cours ou dans les bouquins ont déjà une bonne complexité (la meilleure connue en général): si ton code a la même complexité que le code sur le papier c'est déjà que ton projet est bien ficelé.

Il y a eu récemment une discussion sur les améliorations possibles de Dijkstra mais je ne sais pas si c'est ce que tu cherches...
http://www.developpez.net/forums/viewtopic.php?t=417123

Je cherches juste des algos de ceux écrit dans le sujet qui soient le plus efficace possible pour mon projet de C.
Plus l'algo est rapide,plus la note obtenue sera élévée.
Si tu me dis que dans les livres,je trouverais mon bonheur,j'irais voir à la bibliothèque de ma fac voir ce que je trouve.
Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.

[FrancisSourd]

Plus l'algo est rapide,plus la note obtenue sera élévée.

Il est violent ton prof d'algo

Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.

Ce livre est très bien car très accès sur la programmation. Mais c'est du Delphi.
http://www.univ-valenciennes.fr/sp/sevaux/graphes/

Sur le web, je connais cette implantation en open source
http://www.math.uni-augsburg.de/opt/goblin.html
Mais je doute que la licence t'autorise à rendre ce code à ton prof en mettant ton nom;-) De toute manière, il se doutera de quelque chose!

Mais, pour avoir l'implantation la plus rapide, ce n'est plus forcément une question d'algorithmique et en tout cas pas (plus) une question de complexité. C'est le résultat d'un long travail de programmation et de tests comparant différentes implantations possibles et sélectionnant les meilleurs choix de programmation. Par exemple, selon la densité du graphe, il faudra utiliser une représentation du graphe par une matrice ou par une liste.

[Premium]

Plus l'algo est rapide,plus la note obtenue sera élévée.

Il est violent ton prof d'algo

Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.

Ce livre est très bien car très accès sur la programmation. Mais c'est du Delphi.
http://www.univ-valenciennes.fr/sp/sevaux/graphes/

Sur le web, je connais cette implantation en open source
http://www.math.uni-augsburg.de/opt/goblin.html
Mais je doute que la licence t'autorise à rendre ce code à ton prof en mettant ton nom;-) De toute manière, il se doutera de quelque chose!

Mais, pour avoir l'implantation la plus rapide, ce n'est plus forcément une question d'algorithmique et en tout cas pas (plus) une question de complexité. C'est le résultat d'un long travail de programmation et de tests comparant différentes implantations possibles et sélectionnant les meilleurs choix de programmation. Par exemple, selon la densité du graphe, il faudra utiliser une représentation du graphe par une matrice ou par une liste.

CEci n'est pas un problème car je dois implémenter ces algos avec une matrice et un liste.

[Sib]

Pour ma part, notre prof d'algorithmique nous conseille vivement Introduction à l'Algorithmique de Thomas H. Cormen, qui est en quelque sorte sa bible..
Il l'utilise d'ailleurs pour faire son cours..

On y trouve des pseudo-algorithmes de tous les algorithmes que tu recherches..
Je pense donc que tu pourrais y trouver ton bonheur en ce qui concerne des algos efficaces ..

Bien sûr, il te reviendra la tâche de les implémenter en C !

[Premium]

Bonjour,

concernant les différents algos que je dois coder,je voudrais savoir quelle est la structure (matrice ou liste ) qui convient le mieux pour chacun des algos.
Si quelqu'un pouvait me l'indiquer,ce serait sympa.

Merci d'avance

[Sib]

Hop, petite liste (à toi de trouver les façons de les implémenter ) :

- Prim : Une file de priorité sous la forme d'un tas de Fibonacci
- Kruskal : Une structure de données d'ensembles disjoints (Union-Find structure)
- Dijkstra : Une file de priorité sous la forme d'un tas de Fibonacci

Pour les autres je ne sais pas, mais je suppose que Bellman-Ford utilise lui aussi une file de priorité, à cela près qu'elle doit aussi gérer les clés négatives..

De toute facon, tous ces algorithmes, ainsi que toutes les structures nécessaires à l'exécution de ces algorithmes de manière optimale sont expliqués dans le livre de Cormen (la bible de l'Algorithmique lol)

[Mestoph]

C'est une réponse un peut tardive, mes je viens de coder l'algoritme de warshall pour un besoin personnel...

Le voila :

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
{===============================================================================
  Convertion d'une valeur boolean en byte
===============================================================================}
Function BoolToByte(Valeur : Boolean) : Byte;
Begin
  If Valeur Then Result := 1
  Else Result := 0;
End;
{===============================================================================
  Convertion d'une valeur byte en boolean
===============================================================================}
Function ByteToBool(Valeur : Byte) : Boolean;
Begin
  If Valeur = 1 Then Result := True
  Else Result := False;
End;

Code :

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

1
2
3
4
5
6
7
8
9
  For K := 0 To Length(Tbl) - 1 Do
    For i := 0 To Length(Tbl) - 1 Do
      Begin
        If Tbl[I, K] Then
          For J := 0 To Length(Tbl) - 1 Do
            Begin
              Tbl[I, j] := ByteToBool(BoolToByte(Tbl[I, J]) Or BoolToByte(Tbl[K, J]));
            End;
      End;

A savoir que Tbl est un tableau dynamique de type : Array of Array Of Boolean.

J'èspere qu'il sera utile a quelqu'un