J'ai vu certaines variantes de ce problème décrites sur ce site Web, mais pas exactement celle-ci.

Le problème

J'ai un graphe non pondéré G=(V,E), et de préférence j'ai besoin de faire une solution qui fonctionne à la fois pour les graphes orientés et non orientés.

Un sous-ensemble de V est W, et ce sont des nœuds spéciaux. J'ai besoin de savoir s'il est possible de trouver un chemin d'un nœud de départ s à un nœud de fin t, qui passe par un ou plusieurs des nœuds spéciaux de W. C'est un chemin simple où les nœuds ne sont pas répétés, et il doit fonctionner en temps polynomial

J'ai donc simplement besoin de sortir "vrai" ou "faux".

Ma tentative jusqu'à présent

Tout d'abord, j'ai pensé que pour chaque nœud spécial i W, j'exécuterais un bfs, qui pourrait trouver ce nœud w, puis exécuter un nouveau bfs du nœud w à t. À peu près comme ça :

for w in W:
    firstpath = bfs from s to w
    secondPath = bfs from w to t (that does not touch nodes in firstpath)
    if firstpath + second == path from s to t:
         return True
    else:
        continue

Mais ici, un problème pourrait être que le "premier chemin" pourrait bloquer un chemin possible de w à t.

Des idées d'algorithmes polynomiaux pour ce problème qui pourraient garantir l'absence de "collisions de nœuds"

1
n00bster 3 nov. 2020 à 20:40

1 réponse

Meilleure réponse

Pour les graphes non orientés, nous pouvons essayer tout w dans W, en recherchant deux chemins de nœuds disjoints de w à s et t en utilisant max flow. Je ne suis pas sûr que cela se généralise aux graphes orientés, malheureusement.

1
David Eisenstat 3 nov. 2020 à 18:25