Dijkstra's Shortest Path Calc APK

[1.2] Bug Fixes and Improvements

Instructions:

1. Définissez le nombre total de noeuds
2. Ajouter des informations sur la distance d'un noeud à un autre et cliquez sur. Si vous faites une erreur, cliquez sur la ligne pour le supprimer.
3. Assurez-vous que la et "De" les valeurs sont inférieures au nombre de nœuds.
4. Réglez le noeud de départ. Doit être compris entre 1 et le nombre de nœuds. Par défaut est 0
5. Cliquez sur "Calculer" pour voir la distance du nœud 1 au reste des nœuds!
6. App taux pour soutenir développeur

Vous pouvez demander des fonctionnalités supplémentaires.

L'algorithme de Dijkstra, conçu par l'informaticien Edsger Dijkstra en 1956 et publié en 1959, [1] [2] est un algorithme pour trouver les chemins les plus courts entre les noeuds dans le graphique (qui peuvent représenter, par exemple, les réseaux routiers). L'algorithme existe dans de nombreuses variantes; Variante originale de Dijkstra trouvé le plus court chemin entre deux nœuds, [2], mais une variante plus commune fixe un seul noeud comme la "source" noeud et trouve chemins les plus courts de la source à tous les autres noeuds dans le graphe, la production d'un arbre de plus court chemin.

 1 fonction Dijkstra (graphique, source):
 2
 3 dist [source] ← 0 // Distance de la source à la source
 4 prev [source] ← undefined // noeud précédent dans le chemin optimal initialisation
 5
 6 pour chaque sommet v dans le graphique: // Initialisation
 7 si la source v ≠ v // Si n'a pas encore été retirée de Q (noeuds non visités)
 8 dist [v] ← infini // fonction de distance Inconnu de la source à v
 9 prev [v] ← undefined // noeud Précédente dans la trajectoire optimale de la source
10 fin si
11 v ajouter à Q // Tous les nœuds initialement dans Q (nœuds non visités)
12 fin pour
13
14, tandis que Q est pas vide:
15 u ← sommet de Q min avec dist [u] noeud Source // dans le premier cas
16 retirer u de Q
17
18 pour chaque voisin de v u: // où v est encore à Q.
19 alt ← dist [u] + longueur (u, v)
20 si alt 21 dist [v] ← alt
22 prev [v] ← u
23 fin si
24 fin pour
25 fin tout
26
27 retour dist [], prev []
28
Fonction 29 d'extrémité

Source: Wikipedia