Aller au contenu
View in the app

A better way to browse. Learn more.
Next

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

Algorithme des graphes

Par Sarvok
dans Programmation et Lignes de code

Featured Replies

Posté(e)

Hello,

Mon école me demande de faire un projet assez courant : on a un réseau de transport d'une ville et il faut trouver le plus cours chemin à partir des arrêts fournis par l'utilisateurs.

J'aurais quelques questions :

  1. Déjà pour la réprésentation du graphe, on me propose de le faire soit en liste, soit en matrice. Je crois que pour un réseau fortement connexe il vaut mieux utiliser les matrices et pour les réseaux faiblement connexes, utiliser les listes ? D'autres facteurs sont à prendre en considération pour le choix d'une ou d'une autre représentation ?
  2. Ensuite pour l'algorithme du plus cours chemin, je peux utiliser Floyd, Bellman ou Dijkstra. La différence s'effectue au niveau de la complexité temporelle/spaciale ? Est-ce que, selon la connexité, il vaut mieux en utiliser un en particulier ?

D'avance, merci

  • Citer
    • Posté(e)

    Pour ce qui est de la représentation, tu as tout bon.

    L'autre facteur est la complexité du code. Travailler avec les matrices est plus compliqué qu'avec des listes.

    Pour l'algo à utiliser, la complexité ne dépend pas de la connexité (si ma mémoire est bonne) mais de la taille de ton graphe (nombre de noeuds)... Dijkstra reste le plus facile à implémenter :ouioui:

  • Citer

    • Archivé

    Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

    Aller sur la liste des sujets

    Configure browser push notifications
    Chrome (Android)
    1. Tap the lock icon next to the address bar.
    2. Tap Permissions → Notifications.
    3. Adjust your preference.
    Chrome (Desktop)
    1. Click the padlock icon in the address bar.
    2. Select Site settings.
    3. Find Notifications and adjust your preference.