Introduction

When solving the two-vertex vs. shortest path problem, I investigated how to find a path that is not the shortest but satisfies the condition, so I will leave it as a memo.

procedure

1. Creating an adjacency matrix

Since this data is saved in .csv file, read it using pandas and convert it to numpy array.

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

2. Create a graph with NetworkX.

NetworkX is a Python package for performing graph / network theory calculations.

G=nx.from_numpy_matrix(data)

3. Find and print all the paths that connect the two specified points.

The function used is nx.all_simple_paths (). This function finds all the paths connecting the two specified points by specifying the start point (= source) and the goal point (= target) in the graph G created earlier. However, if it is not a directed graph, especially if it is a huge graph, you will find tens of thousands of paths, so you need to limit the depth of the paths with cutoff.

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

The result is this, Since the read data is huge with 8000 nodes, I limited the path depth to 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]

Finally

The code itself is very simple, but the point I got stuck in is that if you don't limit the depth of the path, the program won't end. I hope it will be helpful for those who are working on similar issues.