在数据框中查找城市之间的最短值 [英] Finding shortest values between the cities in a dataframe

问题描述

我有一个数据框，其中包含城市以及每个城市与其他城市之间的距离.我的数据集看起来像

df

 从城市A城市B城市C城市D城市A 2166 577 175B城市2166 1806 2092城市C 577 1806 653城市D 175 2092 653 

我打算游览所有城市，因此我试图找出可以按最短距离旅行的城市顺序.我想以一个起始位置结束.起点和终点应该相同.

是否可以找到所有城市之间的最短距离，或者可以使用其他任何方法.请帮忙.

解决方案

最新答案.我一直面临着同样的问题.使用

取下幂幂三角矩阵(平方对称距离矩阵)

 #取下幂幂三角矩阵lower_nilpotent_triangular_df = pd.DataFrame(np.tril(df)，column = df.columns，索引= df.index)打印(lower_nilpotent_triangular_df)A B C DA 0.0 0.0 0.0 0.0B 2166.0 0.0 0.0 0.0C 577.0 1806.0 0.0 0.0D 175.0 2092.0 653.0 0.0 

 #遮罩遮罩= np.zeros_like(lower_nilpotent_triangular_df)mask [np.triu_indices_from(mask)] =真#绘制矩阵sns.heatmap(lower_nilpotent_triangular_df，annot = True，fmt ='.0f'，cmap ="YlGnBu"，mask = mask)plt.show() 

解决循环旅行商问题

 #解决圆形最短路径#注意:由于它是圆形的，所以端点=(0,0)#等于端点=(1,1)等...路径= solve_tsp(lower_nilpotent_triangular_df.to_numpy()，端点=(0，0))path_len = path_cost(lower_nilpotent_triangular_df.to_numpy()，路径)#从df获取路径标签path_labels = df.columns [path] .to_numpy()打印('最短循环路径:'，path_labels)打印('路径长度:'，path_len)最短的圆形路径:['A''D'B'C'A']路径长度:4650.0 

绘制路径最短的图

 #定义图形边缘宽度shortest_path_widths = df.copy(deep = True)shortest_path_widths.loc [:，:] = .25对于zip中的idx0，idx1(path_labels [:-1]，path_labels [1:]):shortest_path_widths.loc [idx0，idx1] = 4.shortest_path_widths.loc [idx1，idx0] = 4. 

 #显示图表G = nx.DiGraph()对于Lower_nilpotent_triangular_df.columns中的r:对于lower_nilpotent_triangular_df.index中的c:如果不是lower_nilpotent_triangular_df.loc [r，c]:继续G.add_edge(r，c，#缩放的边长长度= lower_nilpotent_triangular_df.loc [r，c]/250，#边缘标签label = int(lower_nilpotent_triangular_df.loc [r，c])，#没有方向dir ='none'，#边缘宽度penwidth = shortest_path_widths.loc [r，c])#添加属性对于G.edges中的u，v，d(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"，形状=圆形"，高度= .4，fixedsize = True)A.edge_attr.update(color ="black"，fontsize = 10)A.draw('cities.png'，format ='png'，prog ='neato')#在Jupyter Notebook中显示图像图片('cities.png') 

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.

解决方案

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')

这篇关于在数据框中查找城市之间的最短值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！