Discussion :

[atlasm]

bonjour si c possible de m aider ca serait super sympas a bientot


calculer le plus court chemin entre 2 sommets d'un graphe valué
on appelle graphe un ensemble de points ( les sommets)orientés , joignant toujours 2 sommets.on affecte à chaque arc une valeur appartenant a R: sa longueur
un chemin entre deux sommets est une suite consécutive
prenons dans le bon sens ; sa longueur = somme de celles des arcs

[a.a.a]

les algos les plus connus sont
dijkstra, belman, ford fulkerson...

pour le calcul des plus court chemins.
il faut que ton graphe n'ait pas un cycle(circuit) de poids(la somme des valeurs des arcs qui le composent) < 0.
sinon ca boucle.

d'apres ce que j'ai compri, tu cherches un algo pour les graphes orientés valués dans R, ()

si tu as le choix de l'algo, je te conseille dijkstra qui est tres facile a comprendre

dans quel langage cherches-tu le programme?
donne plus de precision sur ce que tu cherches

[atlasm]

les algos les plus connus sont
dijkstra, belman, ford fulkerson...

pour le calcul des plus court chemins.
il faut que ton graphe n'ait pas un cycle(circuit) de poids(la somme des valeurs des arcs qui le composent) < 0.
sinon ca boucle.

d'apres ce que j'ai compri, tu cherches un algo pour les graphes orientés valués dans R, ()

si tu as le choix de l'algo, je te conseille dijkstra qui est tres facile a comprendre

dans quel langage cherches-tu le programme?
donne plus de precision sur ce que tu cherches

je recherche le prog en francais si c est possible et merci bcp pour l aide

[a.a.a]

d'apres ce que j'ai compri, tu cherches pas a le programmer.
tu veux juste savoir comment ca fonctionne.
lequel tu veux au juste : dijkstra?
a toi.

algorithme dijkstra dans google ca donne ca entre autre:

http://www.nimbustier.net/publications/djikstra/
l'explication implementation et ...
bon courage.

[fastzombi]

SLT
moi j'ai programmé l'algo de ford en pascal mais je teste pas les longueur negatives et le circuit sinon ca marche. mon bléme c'est avec bellman la representation en memoire et tout donc HELP.
A+

[lgirard]

la représentation mémoire n'a rien a voir avec l'algo de Bellman !!

Bellman est bcp plus simple à implémenter que Dijkstra, même si ce dernier n'est pas vraiment compliqué.
De plus Bellman de base détecte les circuits négatifs....

Rappel : ces algo déterminent les plus courts chemins d'un point vers tous les autres du graphe. Penseer donc à la condition d'arrêt pour accélerer le calcul du PCC d'un sommet vers un autre.

[fastzombi]

slt
comment ca la representation en memoire n'a rien avoir avec l'algo ??!!! :
donc je fais l'algo de bellman et pour entrer le graphe je le dessine sur une feuille et je le met sur l'ecran comme ca c'est sure aucun probléme de structure de données.
A+

[lgirard]

par définition l'algorithmique est totalement sur papier.... sur PC c'est ensuite la programmation d'un algorithme..
tout est dans la nuance

[fastzombi]

Ok
si t'a bien lu mon msg ca commence par "j'ai programmé" donc je parle bien de programmation. pour la nuance ca le fait mais bon. Avant de programmer un algo il faut le faire sur papier comme tu dit. Le vrai probléme c que mon tp est bizaroide ouia on me demande faire l'algo de ford d'un grpahe representé par son tableau d'adjacence et bellman d'un graphe representé pas sa matrice d'adjacence alors que pour moi ca veut rien dire tableau matrice

A+ :

[tomtom7]

Liste d'adjacence OK
Matrice d'adjacence OK
Tableau d'adjacence

Hypothèse : Tableau d'adjacence = Matrice d'adjacence

Rmq : lgirard a raison... La notion de matrice d'adjacence a un sens ici, son implémentation non.

[fastzombi]

slt
matrice d'adjacence
matrice qui contient les sommets et dans les cases d'intersection des 0 ou des 1 ensuite comment je lit les longueurs ? je le fait separement ?
je peut mettre les longueur directement a la place des 1 mais c plus une matrice d'adjacence non ?
A+

[tomtom7]

slt
je peut mettre les longueur directement a la place des 1 mais c plus une matrice d'adjacence non ?
A+

Ben je dirais que si...
L'info se retrouve de la même manière.

[a.a.a]

matrice d'adjacence implique dimension n*n
c pas bon ca,
sauf si la matrice est pleine.
c a dire un gros graphe en nombre d'arcs.
j'ai jamais vu un exemple d'applications qui utilise ca

rem : la discussion a derivé un peu.

[tomtom7]

Bon ou pas si c'est le but du TP...
Moi j'en ai déjà utilisé. Ca a un énorme avantage c'est que l'accès à l'information est immédiat. Pour des calculs puissants cela peut être très intéressant...

[duffman]

(n'oubliez pas que Dijkstra ne fonctionne que sur des graphes à couts positifs)
sinon pour la matrice d'adjacence, tout dépends aussi de la taille du graphe...
jusqu'à une centaine de sommet, c'est largement envisageable (bien que pas très beau d'un point de vue intellectuel) de coder une matrice d'adjacence n*n (en mettant les distances au lieu de 1-0)
Et puis, si le graphe est non-orienté, il n'y a besoin que de la moitié des infos de la matrice..

pour un plus grand nombre de sommet, il vaut mieux faire une liste, plus dur à implémenter, mais plus efficace en terme de place

[tomtom7]

Ce qui est marrant c'est que la plupart des gens n'évoluent pas avec les PC... (je ne parle pour personne en particulier ici)
Il y a encore5-7 ans avec 32 Mo de RAM c'est clair qu'il fallait faire attention mais aujourd'hui c'est 512 Mo minimum sur une bécane pas exceptionnelle...
Alors même une matrice 1000*1000 c'est vraiment tranquille.

Je n'aide pas à se recentrer sur le sujet... Donc je

[duffman]

bah 1000*1000 c'est tranquille, ca dépends aussi de ce que tu lui demandes:
si tu lui demandes juste de rentrer des nombres et d'afficher la somme des lignes, là ok, ca va pas trop ramer...
mais demande lui un algo en O(n^3) ou O(n²m), tu pourras sentir la différence

[tomtom7]

n'oubliez pas que Dijkstra ne fonctionne que sur des graphes à couts positifs

Dijkstra fonctionne sur un graphe contenant des coûts négatifs sans circuit à coût négatif...

[tomtom7]

bah 1000*1000 c'est tranquille, ca dépends aussi de ce que tu lui demandes:
si tu lui demandes juste de rentrer des nombres et d'afficher la somme des lignes, là ok, ca va pas trop ramer...
mais demande lui un algo en O(n^3) ou O(n²m), tu pourras sentir la différence

Ben c'est ce que je disais... C'est carrément plus rapide.

[duffman]

n'oubliez pas que Dijkstra ne fonctionne que sur des graphes à couts positifs

Dijkstra fonctionne sur un graphe contenant des coûts négatifs sans circuit à coût négatif...

si si...
Le problème du plus court chemin n'a aucun sens dans un graphe avec circuit négatif (car le plus court chemin c'est -infini) bien que l'algo de Bellman détecte les circuits de couts nég...là dessus ok..

En revanche Dijkstra (qui est plus efficace en terme de complexité que Bellman) n'est pas optimal sur des graphes comportant des couts négatifs.. je suis sur de moi

c'est même écrit là dedans

http://www.emse.fr/~micheluc/COURS/GR/DOC/thgr009.html

dans la plupart des pages, ils oublient de le dire...