Qu'est-ce qu'un chemin minimal dans un graphique?

Question

Dans la théorie des graphes, quelle est la distinction entre la distance minimale (que l’algorithme de Dijkstra trouve) et le chemin minimal (dont je ne suis pas sûr de ce qu’il s’agit)?

Answer 1

Le chemin minimal est l'ensemble des arêtes qui, lorsqu'elles sont parcourues, couvrent le moins de distance possible entre deux arêtes. La distance minimale est la somme de la distance entre les arêtes d’un chemin minimal.

Answer 2

distance est scalaire; un numéro. path est une liste de paires de sommets / arêtes?

Answer 3

Distance minimale = somme la plus petite des poids de bord. Chemin minimal = moins d'arêtes.

C'est-à-dire // C'est un trajet plus court entre Vancouver et Toronto, puis vers Winipeg, bien qu'il soit plus court entre Vancouver, Calgary, Regina et ensuite vers Winipeg.

Edit: Retournez ça, je pense.

Answer 4

Je ne suis pas sûr à 100%, mais il semble que le chemin minimal soit la liste des sommets visités lors du franchissement du chemin de distance minimale du sommet A au sommet B.

Answer 5

Permettez-moi de répondre à cette question dans le cadre d’un réseau avec une source et un collecteur. Je voudrais faire la distinction entre un chemin le plus court et un chemin minimal, où un chemin est défini par un ensemble d'arêtes.

Un chemin le plus court est un chemin de la source au puits qui a la distance correspondante la plus courte. Un chemin minimal peut être n’importe quel chemin reliant la source au récepteur tant que

i) il ne contient aucun cycle; et

ii) la suppression de l'un des bords du chemin signifie qu'il n'y a plus de connexion entre la source et le puits.

Answer 6

La distance minimale est identique au chemin minimal.