【Project Euler】Problem 83: 経路の最小値（４方向）

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 83.経路の最小値（４方向）

原文 Problem 83: Path sum: four ways

問題の要約：ファイルから読み込んだマトリクスの左上から右下まで上下左右4方向の動きで到達したときの経路の数の和の最小値を求めよ

今回は4方向ということで今までのアルゴリズムが使えないので、最初から問題 81で使ったnetworkXのsingle_source_dijkstraを使います。すると違いはあまりなく4方向のedgeデータを作るだけで解くことが出来ました。

今回は元のデータの周りに十分大きな値infvを加えていないので、はじのノードのedgeの処理を考える必要があります。ファイルの読み込みは問題 82と同じなので省略します。

# networkXのsingle_source_dijkstraを使って解く（target nodeの値をedgeの重みとして使った）
from itertools import product
import networkx as nx
def nodeName(node):
  return str(node[0])+'-'+str(node[1])

def edgeData(n1,n2):  # node1, node2,
  return [nodeName(n1), nodeName(n2), mtx[n2[0]][n2[1]]]  # use node2 value as edge weight

wedge_list = []
for (y,x) in product(range(msize),repeat=2):
    if x > 0      : wedge_list.append(edgeData((y,x),(y,x-1)))  # left
    if x < msize-1: wedge_list.append(edgeData((y,x),(y,x+1)))  # right
    if y < msize-1: wedge_list.append(edgeData((y,x),(y+1,x)))  # down
    if y > 0:       wedge_list.append(edgeData((y,x),(y-1,x)))  # up

#--- Create the graph from nodes/edges
G = nx.DiGraph()
G.add_weighted_edges_from(wedge_list)

length, path = nx.single_source_dijkstra(G,nodeName((0,0)),nodeName((msize-1,msize-1)))
print(f"answer is : {length+mtx[0][0]}")
print(path)

（開発環境：Google Colab）