Vue d’ensemble

Le problème du plus court chemin à source unique (SSSP) consiste à calculer, pour chaque node accessible depuis le node source, le chemin le plus court avec le poids total minimal des edges parmi tous les chemins possibles ; ou dans le cas des graph non pondérés, le chemin le plus court avec le nombre minimal d'edges. Le coût (ou la distance) du chemin le plus court est le poids total des edges ou le nombre d'edges.

L'algorithme original de Dijkstra a été conçu par le scientifique en informatique néerlandais Edsger W. Dijkstra en 1956 pour trouver le plus court chemin entre deux nodes donnés. Le plus court chemin à source unique est une variante courante, facilitant la planification efficace des chemins et l'analyse des réseaux.

Concepts

Plus Court Chemin à Source Unique de Dijkstra

Voici l'implémentation de base de l'algorithme de Plus Court Chemin à Source Unique de Dijkstra, accompagnée d'un exemple pour calculer les chemins les plus courts pondérés dans un graph non orienté à partir du node source b :

1. Créer une file de priorité pour stocker les nodes et leurs distances correspondantes par rapport au node source. Initialiser la distance du node source à 0 et les distances de tous les autres nodes à l'infini. Tous les nodes sont marqués comme non visités.

2. Extraire le node avec la distance minimale de la file et le marquer comme visité, relaxer tous ses voisins non visités.

Le terme relaxation fait référence au processus de mise à jour de la distance d'un node v connecté au node u vers une distance potentiellement plus courte en considérant le chemin via le node u. Plus précisément, la distance du node v est mise à jour à dist(v) = dist(u) + w(u,v), où w(u,v) est le poids de l'edge (u,v). Cette mise à jour est effectuée uniquement si la distance actuelle dist(v) est supérieure à dist(u) + w(u,v).

Une fois qu'un node a été marqué comme visité, son chemin le plus court a été fixé et sa distance ne changera plus pendant le reste de l'algorithme. L'algorithme ne met à jour que les distances des nodes qui n'ont pas encore été visités.

3. Répéter l'étape 2 jusqu'à ce que tous les nodes soient visités.

Considérations

• L'algorithme de Dijkstra n'est applicable qu'aux graph avec des poids d'edge non négatifs. Si des poids négatifs sont présents, l'algorithme de Dijkstra pourrait produire des résultats erronés. Dans ce cas, un algorithme différent comme le SPFA devrait être utilisé.
• Si plusieurs plus courts chemins existent entre deux nodes, tous seront trouvés.
• Dans les graph déconnectés, l'algorithme ne renvoie que les plus courts chemins du node source à tous les nodes appartenant à la même composante connectée que le node source.

Syntaxe

• Commande : algo(sssp)
• Paramètres :

Exemples

Le graph exemple est le suivant :

File Writeback

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value'
}).write({
  file: {
    filename: 'costs'
  }
})

Résultats : Fichier costs

G,8
F,4
E,5
D,5
C,5
B,2
A,0

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'dijkstra',
  record_path: 1
}).write({
  file: {
    filename: 'paths'
  }
})

Résultats : Fichier paths

A--[102]--F--[107]--E--[109]--G
A--[102]--F--[107]--E
A--[101]--B--[105]--D
A--[101]--B--[104]--C
A--[102]--F
A--[101]--B
A

Direct Return

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'dijkstra',
  record_path: 0,
  order: 'desc'
}) as costs
return costs

Résultats : costs

algo(sssp).params({
  ids: 'A',
  edge_schema_property: '@default.value',
  direction: 'out',
  record_path: 1, 
  order: 'asc'
}) as paths
return paths

Résultats : paths

Stream Return

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'dijkstra'
}).stream() as costs
where costs.totalCost <> [0,5]
return costs

Résultats : costs

algo(sssp).params({
  ids: 'A',
  edge_schema_property: '@default.value',
  record_path: 1
}).stream() as p
where length(p) <> [0,3]
return p

Résultats : p