How to receive the complete path from Networkx shortest path algorithms

Question

I am using floyd_warshall_predecessor_and_distance function of Networkx in Python 3 to find the shortest path on a bidirected graph. The function returns the shortest distance between given two nodes (if there exist an edge) and a portion of the path. I will clarify what I mean by saying "a portion." Following is my input and output.

Input:

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(0)
V = [1, 2, 3, 4, 5]
N = [(i,j) for i in V for j in V if i!=j]
E = {} #Creating an empty dictionary to store the travel times from node i to j
Elist = (list(np.random.randint(low=1, high = 30, size = len(N))))
for i in range(len(N)):
    E[N[i]] = Elist[i] # (i,j) does not have to be equal to (j,i)
E[(2, 1)] = 5
E[(5, 4)] = 0
E[(2, 4)] = 20
G=nx.DiGraph()
G.add_nodes_from(V)
for i in E:
    G.add_weighted_edges_from([(i[0], i[1], E[i])])
path_lengths=nx.floyd_warshall_predecessor_and_distance(G, weight='weight')
path_lengths

Output:

({1: {2: 1, 3: 4, 4: 5, 5: 1},
  2: {1: 2, 3: 4, 4: 5, 5: 1},
  3: {1: 3, 2: 3, 4: 5, 5: 1},
  4: {1: 4, 2: 1, 3: 4, 5: 1},
  5: {1: 4, 2: 5, 3: 4, 4: 5}},
 {1: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {1: 0, 2: 13, 3: 8, 4: 1, 5: 1}),
  2: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {2: 0, 1: 5, 3: 13, 4: 6, 5: 6}),
  3: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {3: 0, 1: 10, 2: 20, 4: 11, 5: 11}),
  4: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {4: 0, 1: 5, 2: 18, 3: 7, 5: 6}),
  5: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {5: 0, 1: 5, 2: 13, 3: 7, 4: 0})})

I intentionally made a path for (2, 4) which is 2 > 1 > 5 > 4. When I look at path_lengths[0], I can see that to go from nodes 2 to 4, I stopped by 5. Further, to go from 2 to 5, I stopped by 1. These two tells me the complete route, but I want to see the whole route as an output, e.g., 2: {... 4: 1, 5, ...} or {(2,4): (2,1), (1,5), (5,4)} rather than seeing it in portion and then combining the pieces in mind. Is there any better package in Networkx that can possibly do this? By the way, my bidirected graph does not involve negative weights and the graph can be quite large (which is why I chose this function).

Here is my attempt to begin:

new = path_lengths[0]
for v in V:
    for d in V:
        if v!=d:
            if new[v][d] != v:
                new[v][d] = (new[v][d],d)
            elif new[v][d] == v:
                new[v][d] = (v,d)

Thanks for responses!

Answer 1

I found the solution to the problem. The following code creates two dictionaries. For paths, the keys denote the arcs and the values show the consecutive arcs needed to be taken for the shortest path. For shortest_distance, the keys denote the arcs and the values show the shortest distance. I am leaving this here for future reference.

Input:

def arcs(seq, n):
    return [seq[max(i, 0):i + n] for i in range(-n + 1, len(seq))]
paths = {}; shortest_distance = {}
for v in V:
    for d in V:
        if v!=d:
            path = nx.single_source_dijkstra_path(G,v)
            paths[(v,d)] = path[d]
for i in paths:
    paths[i] = (arcs(paths[i],2)[1:-1])
    shortest_distance[(i[0],i[1])] = path_lengths[1][i[0]][i[1]]
    for j in range(len(paths[i])):
        paths[i][j] = tuple(paths[i][j])    
for i in paths:
    print(i, paths[i], shortest_distance[i])

Output:

(1, 2) [(1, 2)] 13
(1, 3) [(1, 5), (5, 4), (4, 3)] 8
(1, 4) [(1, 5), (5, 4)] 1
(1, 5) [(1, 5)] 1
(2, 1) [(2, 1)] 5
(2, 3) [(2, 1), (1, 5), (5, 4), (4, 3)] 13
(2, 4) [(2, 1), (1, 5), (5, 4)] 6
(2, 5) [(2, 1), (1, 5)] 6
(3, 1) [(3, 1)] 10
(3, 2) [(3, 2)] 20
(3, 4) [(3, 1), (1, 5), (5, 4)] 11
(3, 5) [(3, 1), (1, 5)] 11
(4, 1) [(4, 1)] 5
(4, 2) [(4, 1), (1, 2)] 18
(4, 3) [(4, 3)] 7
(4, 5) [(4, 1), (1, 5)] 6
(5, 1) [(5, 4), (4, 1)] 5
(5, 2) [(5, 2)] 13
(5, 3) [(5, 4), (4, 3)] 7
(5, 4) [(5, 4)] 0