-3

I am new to the package Networkx. I have the following vertices in V and created edges in N. Then, I randomly assigned some numbers to represent the edge distances and created dict E to store edge and distance info. I want to find the shortest path for each pair of nodes by using Floyd-Warshall algorithm. I searched to find some examples but couldn't end up seeing one that I can implement easily. So, I started by learning how to create a graph using "networkx" package.

import networkx as nx
import numpy as np
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
E = {}
Elist = list(np.random.randint(low=10, high = 50, 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)

Here is the code for the graph and a missing application attempt to find the shortest path. I know I have never used the dictionary E, so I should not expect a correct solution. But, I just couldn't understand how to input for nx.floyd_warshall().

G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1])
nx.floyd_warshall(G)
tcokyasar
  • 582
  • 1
  • 9
  • 26
  • 1
    Hi - you've asked multiple questions. The node label question can be answered by looking here: https://stackoverflow.com/questions/28533111/plotting-networkx-graph-with-node-labels-defaulting-to-node-name – Joel Jun 15 '19 at 00:11
  • @Joel thank you so much. I did ask multiple questions, but they should all be simple for the who knows the stuff. – tcokyasar Jun 15 '19 at 02:58
  • I'm not saying that it's hard to answer, but the standard at stackoverflow is that a question should be a single question so that it's useful to others who come later. You're more likely to get an answer if it's clear what single question you want answered (do I have to answer all of them for you to consider it a valid solution, what happens if I answer one and someone else answers the other - which is the "correct" answer?), and there's a risk that your question will be closed for being "too broad". – Joel Jun 15 '19 at 05:21
  • @Joel I admitted your constructive criticism and reduced my question into a single one. – tcokyasar Jun 17 '19 at 02:06

1 Answers1

0

It appears you are putting in the input to nx.floyd_warshall correctly (at least to treat the graph as unweighted), but I suspect you might be wondering about how to handle weights. Here's an example where I've given each edge a random weight whose key is 'distance'.

import networkx as nx
import numpy as np
import random
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1], distance = random.random())
path_lengths=nx.floyd_warshall(G, weight='distance')
print(path_lengths[333092][467979])
>0.5257894083921129

path_lengths (the thing I've named the result of nx.floyd_warshall) is basically a dictionary of dictionaries. path_lengths[u][v] is the shortest path length from u to v.

Note that the default for weight is weight='weight', so if that key is defined, it will be used unless you say otherwise. If not weight is defined, then it treats each edge as weight 1.

Joel
  • 22,598
  • 6
  • 69
  • 93
  • I added the edges with `G.add_edge(N[i][0], N[i][1], distance = E[(N[i][0], N[i][1])])`. But I see the results are misleading. For example, this is the first element of the dict of dicts `333092: defaultdict(...()>, {333092: 0, 467979: 19, 177073: 33, 164786: 22, 178581: 33})` Here is my E dict for 333092. `(333092, 467979): 10, (333092, 177073): 13, (333092, 164786): 13, (333092, 178581): 49` Why it does not give shorthest paths correctly? – tcokyasar Jun 17 '19 at 14:29
  • So, what I mean is that the distance for the shortest path from 333092 to 467979 should be 10 instead of 19. Indeed, when we look at the dict `E`, we see that all numbers yielded by the algorithm are wrong. I also tried `floyd_warshall_predecessor_and_distance()` to see the path and could not really interpret the results. – tcokyasar Jun 17 '19 at 14:39
  • I figured out the problem and found the solution. My graph was created as an undirected one. I had to replace it with `G=nx.DiGraph()` Thank you so much for all the explanation. – tcokyasar Jun 17 '19 at 15:31