Dijkstra en Java

Il faut utiliser l'algorithme de Dijkstra pour calculer le tableau des prédécesseurs et s'en servir récursivement pour aller de la fin recherchée vers le début.

Voici comment on pourrait faire un tel affichage, avec le code que tu as déjà fait :

private static void aff(InputGraph graph, int[] pred, int deb, int cur)
{
    if (cur == deb)
        System.out.print(graph.sommet[cur]);
    else
    {
        aff(graph,pred,deb,pred[cur]);
        System.out.print(" --> "+graph.sommet[cur]);
    }
}
	
public static void afficherPlusCourtChemin(InputGraph graph,int debut, int fin)
{
    aff(graph,Dijkstra.djikstra(graph, debut),debut,fin);
}

Exemple dans ton main : afficherPlusCourtChemin(ex,0,3);

Ce qui donne : "processus --> activité --> phase --> label"

Bonsoir,

Merci KO pour votre réponse mais en sortie je veux un chiffre qui représente le chemin le plus court.

Cordialement

Merci beaucoup KX. C'est très gentil de votre part.

Bonjour ,

Quelqu'un pourriez me dire SVP comment retrouver la profondeur d'un noeud x avec le code que j'ai déjà posté.

Cordialement.

Bonjour tout le monde,

Une question SVP, comment puis-je déterminer le poids entre deux noeuds voisins dans un graphe non orienté et en utilisant Dijkstra (le graphe et l'algorithme de Dijkstra sont déjà définis plus haut).

Merci à vous.

Par poids entre deux noeuds, je veux dire le poids des arêtes qui les séparent. Je m'explique, moi je veux déterminer la proximité sémantique entre deux noeuds quelconque. Pour y arriver, j'ai attribuer des poids aux arêtes. Plus la distance qui sépare les deux noeuds est minimale, plus ces deux noeuds ( concepts dans l'ontologie) se rapprochent sémantiquement, d'ou l'intérêt de Dijkstra (parcourir le chemin minimal). Cependant, il arrive que deux noeuds soient dans le voisinage. C'est ici que je bloque pour déterminer le poids.

Pour moi, deux noeuds liés par une même arête, appartiennent à la même hiérarchie. Par contre, par voisinage je parle de deux noeuds X et Y qui ne sont pas sur la même hiérarchie (ces deux noeuds qui ont forcément un noeud père en commun). Ce que je veux c'est de déterminer le poids entre X et Y.

C'est quoi "un noeud père commun" ?
Ton graphe est non-orienté, donc si X et Y sont sur la même composante connexe, tous les noeuds de cette composante (donc potentiellement tous les noeuds du graphe) seront sur ton voisinage.

Pour le poids entre X et Y, il faudrait effectivement un algorithme de plus court chemin pour passer de noeuds en noeuds, mais je ne suis pas sûr que le cumul doivent se faire par somme, je verrais plutôt un produit de pourcentages, mais je n'ai pas d'éléments qui me permettent de dire que c'est effectivement ça que tu fais...

Voici un exemple de graphe à pourcentages :
Le chemin A-B-C par exemple aurait un poids de 56% obtenu par produit des deux poids A-B et B-C. Vu ce que tu veux faire c'est plus cohérent qu'une somme...

Par contre il faudrait faire une adaptation du graphe pour que représenter tes poids en pourcentage où deux noeuds sont proches s'ils ont un poids d'arêtes élevés. Et une adaptation de l'algorithme pour avoir un calcul de plus long chemin; avec un cumul multiplicatif et non plus additif.

Exemple : entre D et E le chemin D-E est de 60%, le chemin D-A-E de 72% (donc c'est mieux), mais le meilleur chemin c'est D-C-A-E avec 77%.

Ce que je veux c'est de retrouver le poids entre D et B (si je suis votre graphe) et ce ci en suivant le plus court chemin. Dans mon travail, plus deux noeuds aient un poids faible, plus ils sont similaires sémantiquement, c'est pourquoi j'utilise Dijkstra.

Bonjour,

En fait pour calculer la distance sémantique entre deux noeuds, j'ai une formule à appliquer (ce n'est pas simplement une somme des poids). Cependant, une partie de la formule consiste à chercher le chemin minimal entre ces deux noeuds.

Pourquoi que je tourne en rond! Pour moi, l'algorithme de Dijkstra marche très bien pour deux noeuds qui sont sur la même hiérarchie mais il bloque pour deux noeuds voisins (qui ont un noeud subsompant en commun). Par exemple: Le noeud A est connecté à B. B est connecté à C et D ( C et D sont des feuilles). Dijkstra bloque pour retrouver le chemin entre C et D. Vous me comprenez ?

Comment faire à votre avis ? Je ne peux pas tout de même utiliser des pourcentages pour représenter les poids parce que je me base sur le réseau sémantique Wordnet.

Non je vais pas utiliser une mesure de similarité déjà existante. Je vais définir une nouvelle. Pour deux noeuds quelconque, elle est donnée comme suit: 1-( poids/ 2*depth). Je ne vois pas toujours l'utilité des pourcentages.

La similarité cosinus n'était qu'un exemple, de toute façon elle ne s'applique pas à la sémantique.

Les pourcentages permettent de faire un cumul multiplicatif, alors qu'avec tes distances tu es contraint d'utiliser un cumul additif ce qui va te donner des valeurs bizarres.

Je reprends le même graphe mais avec des distances (min=0, max=20)
Si on prends A, B, C, avec un cumul additif on se retrouve avec A-B qui a le même poids (6) que A-C-B, alors qu'avec les pourcentages on avait 70% et 72%, donc c'est sensiblement la même chose pour une arête.

Le problème vient quand on met les arêtes bout à bout alors on se retrouve avec des distances aberrantes, par exemple E-D-A-B-C a une distance de 22 ce qui correspond à un pourcentage négatif (-10%) ce qui n'a aucun sens !
Alors qu'avec les pourcentages on aurait une similarité certes faible (27%) mais qui reste toujours cohérente...

Les poids entre les noeuds de mon graphe varient de 0 à 1, donc je vais pas me retrouver dans cette situation aberrante. Ce que je veux c'est simplement de faire le cumul des poids.

J'ai déjà normalisé ma formule, donc le résultat va toujours être compris entre 0 et 1. En fait, j'ai divisé la somme des poids (chemin du noeud x au noeud y en suivant le plus court chemin) par 2* profondeur du noeud le plus éloigné de la racine.

Non jamais des résultats supérieurs à 1 avec une formule comme 1-(poids/2*profondeur). Par "profondeur du noeud le plus éloigné de la racine", je veux dire le noeud ayant la profondeur la plus grande.

Non, vous m'avez mal compris. Dans ma nouvelle approche, plus deux concepts se rapprochent sémantiquement, moins est la distance; c'est pourquoi j'ai noté le "1-".

Bonjour,

Je me permets de déterrer ce sujet (enfin en vrai, c'est la moulinette qui génère les résumés qui l'a fait) car les réponses proposées me paraissent ne sont pas tout à fait correct.

Tout d'abord l'algorithme de Dijkstra ne devrait pas être implémenté de manière récursive, car cela donnera dans en général soit un résultat faux, soit une boucle infinie.

La théorie

Paramètres

L'algorithme de Dijkstra est paramétré par :

• un graphe (orienté ou non, potentiellement avec des boucles ou des cycles)
• un sommet source
• une algèbre de chemin qui doit vérifier les propriétés d'un semi anneaux.
  • en général, on utilise l'algèbre (R+, min, +) qui signifie que les poids sont des réels positifs, on préfère le chemin le plus court (min), et pour obtenir la longueur d'un chemin, on somme le poids d'un chemin avec celui d'un arc qu'on tente de lui concaténer
  • la plupart des implémentations de l'algorithme de Dijkstra parte du principe que l'algèbre de chemin est "forcément" (R+, min, +), et c'est bien dommage, car l'algorithme est bien plus générique
  • quelques exemples d'algèbres de chemins compatibles avec Dijkstra
    • ([0, 1], max, x) : algèbre de la fiabilité : chaque arc est pondéré par un pourcentage (donc une valeur dans [0, 1]), on cherche le chemin le plus fiable (max), la fiabilité d'un chemin est le produit des poids de ses arcs (x), .
    • (R+, max, min) : algèbre de la bande passante : chaque arc est pondéré par une capacité, on cherche le chemin avec la plus grande bande passante (max), la bande passante d'un chemin est déterminée par l'arc qui joue le rôle de goulot d'étranglement (min)
    • Pour en voir d'autres, cf par exemple les travaux sur le Graphe et algorithmes de Gondran & Minoux, tous les articles scientifiques sur le "Metarouting", etc.

Sorties

L'algorithme de Dijkstra retourne un arbre pondéré de plus courts chemin (enraciné à la source et orienté vers les feuilles dans le cadre d'un graphe orienté) ainsi représenté :

• un vecteur de prédécesseur (on associe à chaque sommet son prédécesseur dans l'arbre de plus court chemin).
  • Dans l'absolu plusieurs plus courts chemins peuvent exister d'un sommet vers un autre. Dans ce cas, l'algorithme de Dijkstra en reconstruit un arbitraire. On peut cependant adapter l'implémentation de l'algorithme pour maintenir un vecteur de prédécesseurs. Dans ce cas, on l'algorithme ainsi modifié retourne un DAG (Directed Acyclic Graph) de plus courts chemin enraciné à la source.
• un vecteur de distance, qui retourne pour chaque sommet le coût pour aller de la source à ce sommet.

Principe

Pour calculer un arbre de plus court chemins, l'algorithme de Dijkstra part de la source et traite le sommet non encore traité le plus proche de la source. On a donc besoin d'une queue à priorité, qui ordonne les sommets à traiter du plus proches au plus éloignés. En effet, selon le principe de sous-optimalité de Dijkstra, lorsqu'on traite les sommets dans cet ordre, on ne revient jamais sur une décision prise par le passé.

Complexité en temps

Le principe de sous-optimalité de Dijkstra permet de garantir que chaque sommet n'a besoin d'être traité qu'une et une seule fois. Dans un graphe G(V, E), en considérant le tri engendré par la queue à priorité (coût log([V|) pour chaque sommet, soit |V|.log(|V|)), et le fait qu'il faut examiner chaque arc (coût |E|), l'algorithme s'exécute en O(|V|.log(|V|) + |E|).

Pour aller plus loin

Intuitivement, quand l'algorithme s'exécute, tout se passe comme si l'on "contaminait" les sommets des plus proches vers les plus éloignés. Pour ce faire, l'algorithme de Dijkstra fait une sorte de Breadth First Search (BFS), mais en examinant les sommets conformément à l'ordre dicté par sa queue à priorité. 

Un des gros danger pour l'algorithme de Dijkstra, c'est précisément d'être pris dans une boucle infinie (typiquement parce qu'un graphe comportant un cycle ou une boucle pourrait amener à traverser cette boucle ou ce cycle un nombre infini de fois). En particulier, si un cycle est absorbant (c'est-à-dire que le traverser permet de diminuer le coût), on a tout intérêt à tourner indéfiniment. C'est là que deux points entrent en jeu :

• Concernant les poids : l'algèbre de chemin garantit qu'un cycle ou une boucle absorbante ne peuvent exister. En effet, pour l'algèbre usuelle (R+, min, +), les poids négatifs sont de facto interdits. Et (R, min, +) (poids positifs ou négatifs n'est pas un semi anneau, donc on n'a pas le droit d'invoquer l'algorithme de Dijkstra.
• Concernant la topologie du graphe : Pour ne traiter chaque sommet qu'une seule fois, on a recours souvent à une structure auxiliaire, appelée color map, qui associe à chaque sommet sont statut (typiquement : traité, en cours de traitement, non traité). Cette color map prend tout son sens si le graphe comporte des boucles et/ou des cycles.

Implémentation de l'algorithme de Dijkstra

• Pseudo code
• En Java

Calcul de la profondeur

Intuitivement, calculer une profondeur est un cas particulier de calcul de plus court chemin avec l'algèbre (R+, min, +) où le poids de tous les arcs vaut 1. On pourrait donc utiliser l'algorithme de Dijkstra, qui s'exécute en O(log(|V|).|V| + |E|).

Cependant on peut faire mieux et obtenir le même résultat plus rapidement, en O(|V| + |E|). Il suffit pour cela d'utiliser un algorithme de parcours de graphe, soit un BFS (Breadth First Search), soit un DFS (Depth First Search).

Dans ce fil de discussion, il faut donc :

1. Exécuter un DFS/BFS pour intégrer la profondeur aux poids prédéfinis.
2. Exécuter l'algorithme de Dijkstra sur ce nouveau jeu de poids.

Bonne chance