Einführung

Bei der Lösung des Problems mit zwei vertikalen bis kürzesten Pfaden habe ich untersucht, wie ein Pfad gefunden werden kann, der nicht der kürzeste ist, aber die Bedingung erfüllt. Daher werde ich ihn als Memo belassen.

Verfahren

1. Erstellen einer benachbarten Matrix

Da diese Daten in einer CSV-Datei gespeichert sind, lesen Sie sie mit Pandas und konvertieren Sie sie in ein Numpy-Array.

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

2. Erstellen Sie mit NetworkX ein Diagramm.

NetworkX ist ein Python-Paket zur Durchführung von Berechnungen der Graph- / Netzwerktheorie.

G=nx.from_numpy_matrix(data)

3. Suchen und drucken Sie alle Pfade, die die beiden angegebenen Punkte verbinden.

Die verwendete Funktion ist nx.all_simple_paths (). Diese Funktion findet alle Pfade, die die beiden angegebenen Punkte verbinden, indem der Startpunkt (= Quelle) und der Zielpunkt (= Ziel) in dem zuvor erstellten Diagramm G angegeben werden. Wenn es sich jedoch nicht um ein gerichtetes Diagramm handelt, insbesondere wenn es sich um ein großes Diagramm handelt, finden Sie Zehntausende von Pfaden. Daher müssen Sie die Tiefe des Pfads mit einem Cutoff begrenzen.

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

Das Ergebnis ist dies, Da die gelesenen Daten mit 8000 Knoten sehr groß sind, habe ich die Pfadtiefe auf 13 begrenzt.

[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]

Schließlich

Der Code selbst ist sehr einfach, aber der Punkt, an dem ich feststeckte, ist, dass das Programm nicht endet, wenn Sie die Tiefe des Pfades nicht begrenzen. Ich hoffe, es ist hilfreich für diejenigen, die an ähnlichen Themen arbeiten.