introduction

Lors de la résolution du problème des deux chemins verticaux par rapport au plus court, j'ai étudié comment trouver un chemin qui n'est pas le plus court mais qui satisfait la condition, je vais donc le laisser comme mémo.

procédure

1. Création d'une matrice adjacente

Étant donné que ces données sont enregistrées dans un fichier .csv, lisez-les à l'aide de pandas et convertissez-les en tableau numpy.

file = pd.read_csv('Data1.csv', header=None, delimiter=',')  
data = np.array(file)

2. Créez un graphique avec NetworkX.

NetworkX est un package Python permettant d'effectuer des calculs de théorie des graphes / réseaux.

G=nx.from_numpy_matrix(data)

3. Recherchez et imprimez tous les chemins qui relient les deux points spécifiés.

La fonction utilisée est nx.all_simple_paths (). Cette fonction trouve tous les chemins reliant les deux points spécifiés en spécifiant le point de départ (= source) et le point de but (= cible) dans le graphe G créé précédemment. Cependant, s'il ne s'agit pas d'un graphe orienté, surtout s'il s'agit d'un graphe énorme, vous trouverez des dizaines de milliers de chemins, vous devez donc limiter la profondeur du chemin avec coupure.

for path in nx.all_simple_paths(G,source=1,target=100, cutoff=13): 
	print(path)

Le résultat est le suivant, Étant donné que les données lues sont énormes avec 8000 nœuds, j'ai limité la profondeur du chemin à 13.

[1, 2587, 808, 211, 188, 6510, 6216, 3057, 5276, 1512, 3826, 5203, 100]
[1, 2587, 808, 4675, 1671, 5411, 3983, 3714, 202, 3064, 644, 2182, 100]
[1, 2587, 808, 4675, 1671, 5411, 3983, 6512, 3590, 7915, 2182, 100]
[1, 2587, 808, 4675, 5958, 4521, 6562, 7430, 4083, 6189, 3089, 3826, 5203, 100]
[1, 2587, 6562, 4521, 5958, 4675, 1671, 5411, 3983, 6512, 3590, 7915, 2182, 100]
[1, 2587, 6562, 6046, 4846, 324, 7374, 1141, 3651, 1963, 888, 5203, 100]
[1, 2587, 6562, 7430, 4083, 6189, 3089, 3826, 5203, 100]
[1, 3346, 4986, 4968, 2652, 1750, 5373, 6453, 6667, 5505, 7572, 7915, 2182, 100]
[1, 3346, 4986, 4968, 2652, 2154, 5437, 656, 3987, 2058, 6764, 6790, 2182, 100]
[1, 3346, 4986, 4968, 2652, 2800, 2448, 3575, 1141, 3651, 1963, 888, 5203, 100]
[1, 3346, 4986, 4968, 4197, 7116, 6733, 869, 4783, 6468, 7620, 6790, 2182, 100]
[1, 3346, 4986, 4968, 5331, 1379, 6246, 6214, 40, 2579, 3590, 7915, 2182, 100]
[1, 3346, 4986, 4968, 5331, 7417, 7969, 6865, 2863, 868, 6764, 6790, 2182, 100]

finalement

Le code lui-même est très simple, mais le point dans lequel je suis resté coincé est que si vous ne limitez pas la profondeur du chemin, le programme ne se terminera pas. J'espère que cela sera utile pour ceux qui travaillent sur des questions similaires.