2つの行列間の最短経路

Question

変数名が重複する2つの距離行列があります。

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'sに距離行列をロードし、それらをアンスタッキングすることでこれをプログラムしました。次に、df.itterows（）と2つのforループを使用して、可能な組み合わせをループし、A1 - > Zの組み合わせの最小値を確認してください。

しかし、これは約30000個のアイテムで行います。長いです。

誰もがベクトル化された方法でこれを行う方法を知っていますか？

Answer 1

Dを追加しました。私の便宜のために軸の長さが異なるようになりました（正方形の行列でも動作します）。

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