python-2.7 - 两个矩阵之间的最短路径

Question

我有两个变量名称重叠的距离矩阵。

dfA:

    Start   A1  A2  A3  A4  … A150
Location                        
A           12  4   12  2      9
B           5   2   19  4      3
C           1   4   8   7      12

DFB:

    A   B   C           
X   4   12  32          
Y   1   6   12          
Z   2   8,5 11

因此，从 A1、A2 等开始，通过 ABC，有通往 X、Y 和 Z 的路径

我想看看某个项目的最短路径是什么，例如组合 A1 -> Z。我通过加载带有距离矩阵的 csv 并将其拆开来对此进行编程。然后使用 df.itterows() 和两个 for 循环遍历可能的组合，并查看组合 A1 -> Z 的最小值。

但是由于我必须对大约 30000 个项目执行此操作，因此需要很长时间。

有人知道如何以矢量化方式做到这一点吗？

Answer 1

我添加了D，以便轴长度不同(dfB 不会是方阵)只是为了方便(它也适用于方阵)。

import pandas as pd
import numpy as np
df_a = pd.read_csv('dfA.csv', delim_whitespace=True, index_col=0, decimal=",")
df_b = pd.read_csv('dfB.csv', delim_whitespace=True, index_col=0, decimal=",")
mat_a = df_a.values
mat_b = df_b.values
mat_a2 = np.expand_dims(mat_a, axis=2)
mat_b2 = np.expand_dims(mat_b.T, axis=1)
mat_a3 = np.tile(mat_a2, (1, 1, mat_b.shape[0]))
mat_b3 = np.tile(mat_b2, (1, mat_a.shape[1], 1))
tot = mat_a3 + mat_b3
ind = np.argmin(tot, axis=0).T
df_c = pd.DataFrame(df_b.columns.values[ind], columns=df_a.columns, index=df_b.index)
print(df_c)

dfA:

Start_Location   A1  A2  A3  A4  A150
A                12  4   12  2      9
B                5   2   19  4      3
C                1   4   8   7      12
D                5   2   9   11     4

DFB:

    A   B   C   D
X   4   12  32  11,4
Y   1   6   2  9,3
Z   2   8,5 11  1,4

dfC:

  A1 A2 A3 A4 A150
X  A  A  A  A    A
Y  C  A  C  A    B
Z  D  D  D  A    D