Finding shortest values between the cities in a dataframe

Question

I have a dataframe with cities and distance between other cities from each city. My dataset looks like,

df,

 From City      City A  City B City C  City D
 City A                 2166    577     175
 City B         2166            1806    2092
 City C         577     1806            653
 City D         175     2092    653 

im planning to visit all the cities, I am trying to find in which order by cities I can travel with the shortest distance. I want to end with a starting position. start point and end point should be same.

Is there a way to find this shortest distance across all the cities, or any other approach is available. please help.

Answer 1

Late answer. I've been facing the same problem. Leaving a solution (in case someone needs it) with tsp_solver to solve the TSP and networkx, pygraphviz to plot the results graph.

import numpy as np
import pandas as pd

from tsp_solver.greedy import solve_tsp
from tsp_solver.util import path_cost

import matplotlib.pyplot as plt
import seaborn as sns
import networkx as nx

# for Jupyter Notebook
from IPython.display import Image

Define the distances matrix DataFrame

# Define distances matrix dataframe
df = pd.DataFrame({
    'A': [np.nan, 2166, 577, 175],
    'B': [2166, np.nan, 1806, 2092],
    'C': [577, 1806, np.nan, 653],
    'D': [175, 2092, 653, np.nan]
}, index=['A', 'B', 'C', 'D'])

print(df)

        A       B       C       D
A     NaN  2166.0   577.0   175.0
B  2166.0     NaN  1806.0  2092.0
C   577.0  1806.0     NaN   653.0
D   175.0  2092.0   653.0     NaN

Fill NaNs

# Fill NaNs with 0s
df.fillna(0, inplace=True)
# plot the matrix
sns.heatmap(df, annot=True, fmt='.0f', cmap="YlGnBu")
plt.show()

Take the lower nilpotent triangular matrix (square symmetric distance matrix)

# Take the lower nilpotent triangular matrix
lower_nilpotent_triangular_df = pd.DataFrame(
    np.tril(df),
    columns=df.columns,
    index=df.index
)
print(lower_nilpotent_triangular_df)

        A       B      C    D
A     0.0     0.0    0.0  0.0
B  2166.0     0.0    0.0  0.0
C   577.0  1806.0    0.0  0.0
D   175.0  2092.0  653.0  0.0

# mask
mask = np.zeros_like(lower_nilpotent_triangular_df)
mask[np.triu_indices_from(mask)] = True
# plot the matrix
sns.heatmap(lower_nilpotent_triangular_df, 
            annot=True, fmt='.0f', 
            cmap="YlGnBu", mask=mask)
plt.show()

Solve the circular Traveling Salesman Problem

# Solve the circular shortest path
# NOTE: since it is circular, endpoints=(0,0)
#       is equal to endpoints=(1,1) etc...
path = solve_tsp(lower_nilpotent_triangular_df.to_numpy(), endpoints=(0, 0))
path_len = path_cost(lower_nilpotent_triangular_df.to_numpy(), path)
# Take path labels from df
path_labels = df.columns[path].to_numpy()
print('shortest circular path:', path_labels)
print('path length:', path_len)

shortest circular path: ['A' 'D' 'B' 'C' 'A']
path length: 4650.0

Plot the graph with the shortest path

# Define graph edges widths
shortest_path_widths = df.copy(deep=True)
shortest_path_widths.loc[:,:] = .25
for idx0, idx1 in zip(path_labels[:-1], path_labels[1:]):
    shortest_path_widths.loc[idx0, idx1] = 4.
    shortest_path_widths.loc[idx1, idx0] = 4.

# Show the graph
G = nx.DiGraph()
for r in lower_nilpotent_triangular_df.columns:
    for c in lower_nilpotent_triangular_df.index:
        if not lower_nilpotent_triangular_df.loc[r, c]:
            continue
        G.add_edge(
            r, c,
            # scaled edge length
            length=lower_nilpotent_triangular_df.loc[r, c]/250,
            # edge label
            label=int(lower_nilpotent_triangular_df.loc[r, c]),
            # no direction
            dir='none', 
            # edge width
            penwidth=shortest_path_widths.loc[r, c]
        )

# Add attributes
for u,v,d in G.edges(data=True):
    d['label'] = d.get('label','')
    d['len'] = d.get('length','')
    d['penwidth'] = d.get('penwidth','')

A = nx.nx_agraph.to_agraph(G)
A.node_attr.update(color="skyblue", style="filled", 
                   shape='circle', height=.4, 
                   fixedsize=True)
A.edge_attr.update(color="black", fontsize=10)

A.draw('cities.png', format='png', prog='neato')
# Show image in Jupyter Notebook
Image('cities.png')