Un seul chemin le plus court d'un graphe acyclique non orienté déconnecté

Question

Existe-t-il un algorithme de graphe qui donne un début (v) et une extrémité (u) trouvera le chemin le plus court à travers l'ensemble des arêtes, mais si u est un sommet déconnecté, cela déterminera également le chemin le plus court pour ajouter des bords manquants jusqu'à ce que vous ne soyez plus déconnecté?

J'ai une matrice de pixels où les lignes sont en 255 (noir) et 0 (blanc). les lignes (255) peuvent avoir des cassures ou des éperons et je dois me débarrasser des deux. Je pourrais avoir une forêt de matrice de pixels avec environ 7 arbres de pixels noirs. J'ai besoin de trouver les vrais points extrêmes de chaque arbre, trouver le chemin le plus court de chaque arbre, puis réunir tous les arbres obliques pour former une seule ligne (c.-à-d. Un chemin le plus court parmi les 2 extrémités de la matrice originale) . tous les poids des arêtes peuvent être considérés comme 1.

Merci

Answer 1

Que diriez-vous en cours d'exécution Dijkstra's algorithm et en cas de déconnexion, connectez v et u? Quel est votre critère pour "meilleur endroit pour ajouter un bord manquant?" Les bords ont-ils des poids (comme la distance)?

Modifier: Pour une idée de « le meilleur endroit », vous pouvez essayer le chemin qui a somme minimale de chemins les plus courts entre toutes les paires connectées. Floyd–Warshall algorithm peut être utilisé pour trouver les chemins les plus courts entre toutes les paires. Alors, lancez Floyd-Warshall pour chaque nœud dans l'arbre de v et u.

Answer 2

Votre problème n'est pas bien défini pour les graphiques déconnectés. Je peux toujours ajouter et border entre v et u. Si vous vouliez dire que, étant donné un graphe déconnecté acyclique non orienté, connu comme une forêt, et donné un sous-ensemble de bords comme un sous-graphe, pouvez-vous trouver le chemin le plus court entre sommets, que ce problème est trivial chemin dans le graphe complet, il n'y a qu'un seul chemin.

S'il s'agit d'un graphe général G, et que vous parlez d'un sous-graphe de forêt G ', nous avons besoin de plus d'informations. Est-ce pondéré? Est-ce seulement des poids positifs? Si ce n'est pas pondéré, faites une variante de Dijksta. Définir le diamètre d'un arbre comme étant la longueur du plus long chemin entre deux feuilles (ceci est bien défini dans un arbre, car il n'y en a qu'un seul). Soit S la somme des diamètres de tous les arbres de G ', puis le poids de toutes les arêtes de G' à 2S, alors l'algorithme de Dijkstra préfèrera automatiquement passer par G ', ne dépassant G' que s'il n'y a pas de choix, car marcher à travers G 'serait toujours moins cher.