L'algorithme de Dijkstra pour trouver le chemin le plus pondéré

Question

Je veux juste m'assurer que cela fonctionnerait. Pourriez-vous trouver le meilleur chemin en utilisant l'algorithme de Dijkstra? Auriez-vous besoin d'initialiser la distance à quelque chose comme -1 en premier et ensuite changer le sous-programme de relaxation pour vérifier s'il est plus grand?

Ceci est pour un problème qui n'aura aucun poids négatif.

Ceci est en fait le problème:

Supposons que vous donne un schéma d'un réseau téléphonique, qui est un graphique G dont les sommets représentent des centres de commutateurs, et dont les arêtes représentent des lignes de communication entre deux centres. Les bords sont marqués par leur bande passante de son bord de largeur de bande le plus bas. Donner un algorithme qui, donné un diagramme et deux centres de commutateurs un et b, produira la bande passante maximale d'un chemin entre a et b.

Est-ce que cela fonctionnerait?

---

EDIT:

J'ai trouvé ceci:

Astuce: Le sous-programme de base sera très similaire à la sous-routine Détendez-vous dans Dijkstra. Supposons que nous ayons un bord (u, v). Si min {d [u], w (u, v)}> d [v] alors nous devrions mettre à jour d [v] à min {d [u], w (u, v)} (parce que le chemin d'un à u et puis à v a la bande passante min {d [u], w (u, v)}, ce qui est plus que celui que nous avons actuellement).

Vous ne savez pas exactement ce que cela signifie, car toutes les distances sont infinies à l'initialisation. Donc, je ne sais pas comment cela pourrait fonctionner. des indices?

Answer 1

Je ne suis pas sûr que Djikstra est la voie à suivre. Les poids négatifs font du mal, de mauvaises choses à Djikstra. Je pense que vous pouvez trier par poids de bord, et commencez à supprimer le plus faible poids (le pire goulot d'étranglement), et voir si le graphique est encore connecté (ou au moins vos points de départ et d'arrivée). Le point auquel le graphique est brisé est quand vous savez que vous avez supprimé le goulot d'étranglement, et vous pouvez regarder la valeur de ce bord pour obtenir la bande passante. (Si je ne me trompe pas, chaque itération prend O (E) le temps, et vous aurez besoin O (E) itérations pour trouver le bord de goulot d'étranglement, c'est donc un O (E) algorithme.

Modifier : vous devez comprendre que le plus grand chemin n'est pas nécessairement la plus large bande passante: vous cherchez à maximiser la valeur de min({edges in path}), non sum({edges in path})

Answer 2

Le flux de calcul peut être plus applicable, mais le flux permet d'utiliser plusieurs chemins.

Answer 3

inverser seulement les poids de bord qui est, si le poids de bord est d.. , considérons-le plutôt comme d^-1, alors faites Dijkstra comme d'habitude.Initialisez normalement toutes les distances à l'infini

Answer 4

Vous pouvez utiliser l'algorithme de Dijkstra pour trouver un seul chemin le plus long, mais s Etant donné que vous n'avez que deux centres de commutation, je ne vois pas pourquoi vous devez visiter chaque nœud comme chez Dijkstra. Il y a la plupart des goûts une façon plus optimale d'aller ceci, comme un algorithme de branche et lié.

Answer 5

Vous pouvez résoudre cela facilement en modifiant Dijkstra pour calculer la bande passante maximale à tous les autres sommets.

Vous n'avez pas besoin d'initialiser le sommet de départ à -1. Ce n'est peut-être pas le moyen le plus efficace pour calculer la bande passante, mais c'est ce que je pouvais penser pour l'instant.

Answer 6

Pouvez-vous ajuster une partie de la logique dans l'algorithme AllPairsShortestPaths (Floyd-Warshall)?

Initialiser les arêtes non connectées à l'infini négatif et au lieu de prendre le minimum des distances, prendre le maximum?