Le plus court chemin entre deux nœuds dans un graphe (Java)

J'ai un programme avec un graphique dont les nœuds représentent des processus, et le temps de calcul de processus est le coût du nœud.Ce graphique est maintainded dans la mémoire comme une liste de nœuds et chaque clin d'oeil a une liste de parents et enfants et sa durée d'exécution.

Je dois trouver le chemin d'accès avec la durée d'exécution minimale.

  • Chaque nœud peut se connecter avec n'importe quel autre.
  • Il n'y a qu'un début et une fin noeuds.
  • Un nœud peut avoir diverses « parent » et « enfants »

Quelqu'un peut me dire la meilleure façon de le faire ?

répondre #1

Vous pouvez utiliser l'algorithme de Dijkstra pour cela.

répondre #2

Dijkstra a été mentionné déjà, il y a aussi l' algorithme A * , qui peut être plus performante sous certaines conditions et dont on peut apprendre beaucoup de choses. Il y a aussi un bon livre sur les algorithmes de graphique avec beaucoup d'exemples de code Java par Robert Sedgewick que j'ai trouvé utiles il y a plusieurs années. Le titre est "algorithmes en Java, partie 5: algorithmes graphique".

répondre #3

Un moyen d'y parvenir consiste à utiliser diverses algorithme plus court chemin, tels que l'algorithme de Dijkstra. Pour ce faire, vous devez coder un « tas », une structure de données dans laquelle le nœud avec le plus petit poids-âge est sur le dessus.

L'idée derrière l'algorithme consiste à assurer le suivi de la distance totale dès le départ vers le nœud actuel pour l'itinéraire actuel. L'algorithme glouton habituel est un où vous suffit de sélectionner le nœud voisin par le chemin le plus court. Dijkstra s'étend sur cela en sélectionnant le nœud qui donnerait la plus courte distance globale à partir du nœud de démarrage vers ce nœud.

répondre #4

JGraph a une implémentation de l' algorithme de Dijkstra.

répondre #5

Quelques notes specificly sur l'algorithme de Dijkstra en Java :

http://Renaud.waldura.com/doc/Java/Dijkstra/

Et une note sur les performances :

La complexité de l'algorithme de Dijkstra dépend fortement de la complexité de la file d'attente de priorité Q. Si cette file d'attente est mis en œuvre naïvement que j'ai présenté tout d'abord il (c'est-à-dire commandés à nouveau à chaque itération pour rechercher le nœud mininum), l'algorithme effectue dans désavantageuse, où n est le nombre de nœuds dans le graphique.

Avec une vraie priorité file d'attente gardé ordonnée en tout temps, que nous avons mis en place il, les moyennes de complexité O (n log m). La fonction logarithme découle de la classe de PriorityQueue de collections, une implémentation de tas qui se produit au log(m). Avec une vraie priorité file d'attente gardé ordonnée en tout temps, que nous avons mis en place il, les moyennes de complexité O (n log m).

répondre #6

Master1: (Algorithme de chemin plus courte démo)

Écrire un programme qui illustre graphiquement l'algorithme du plus court chemin. Le programme génère un graphe au hasard et affiche le chemin le plus court entre plusieurs nœuds. Le programme fonctionnera comme suit :

  1. Au hasard, a choisi la taille du graphique (5-15 nœuds).
  2. Réparties de façon aléatoire les nœuds sur un panneau.
  3. Créer au hasard des bords entre les nœuds (le degré de chaque nœud est comprise entre 1 et 3).
  4. Afficher le graphique
  5. Sélectionnez les deux nœuds et mettez-le en surbrillance sur le graphique de manière aléatoire.
  6. Étape par étape construire le plus court chemin entre deux nœuds (utilisez le délai approprié).
  7. Répétez les étapes 5 et 6 pour une autre paire de nœuds. Task2: (Tortue graphique) exerce 7,21 page 298 dans la 9ème édition).

Tâche 3: (Modification de la représentation de données internes d'une classe) il serait tout à fait raisonnable pour la classe Time2 représente le temps en interne comme le nombre de secondes écoulées depuis minuit plutôt que la minute de l'heure de valeurs entières de trois et la deuxième. Les clients pourraient utiliser les mêmes méthodes publiques et obtenir le même résultat. Modifiez la classe Time2 pour mettre en œuvre le temps comme le nombre de secondes écoulées depuis minuit et montrer qu'aucun changement n'est visible pour les clients de la classe.


Tags lesen

     
 
logo_banner