csvファイル内の距離行列の全点間の最短距離の算出

Question

実現したいこと

csvファイル内に距離行列があるが、これをワーシャルフロイド法を用いて全点間の距離を算出し、距離行列を作成したい。
このコードをご教授頂きたいです。

早急にこの距離行列を解かないといけないのですが、実際は2000×2000ぐらいの行列です。

前提

画像のように距離行列がある。
実際は2000×2000の行列である。

発生している問題・エラーメッセージ

エラーメッセージ
indentation error

該当のソースコード

import csv

def warshall_floyd(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

def read_distance_matrix_from_csv(filename):
    with open(filename, 'r') as file:
        reader = csv.reader(file)
        # ヘッダ行をスキップ
        next(reader)
        dist_matrix = [list(map(int, row[1:])) for row in reader]
    return dist_matrix

# CSVファイルから距離行列を読み取る
filename = 'path_to_your_csv_file.csv'
dist = read_distance_matrix_from_csv(filename)

# ワーシャルフロイド法を適用
result = warshall_floyd(dist)

# 結果を表示 (オプション)
# for row in result:
# print(row)

試したこと

「# ヘッダ行をスキップ」の最後の「return dist_matrix」でエラーが起こった

Answer 1

「該当のソースコード」を提示されている CSV ファイルで実行すると，

ValueError: invalid literal for int() with base 10: ''

のエラーが生じました。

これは，空文字列（''）を整数に変換しようとしたことが原因と考えられ，空文字列を特定の数値文字列に置換しておく必要がありますが，今回の目的に合わせて無限大を模した数値文字列 INF = '100000' に置換することにしました。

記述例を下記に示します。

import csv

def warshall_floyd(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

def read_distance_matrix_from_csv(filename):
    with open(filename, 'r', newline='') as csvfile:
        reader = csv.reader(csvfile)
        return [row[1:] for i, row in enumerate(reader) if i > 0]

file_name = 'sample.csv'
INF = '100000'

d_csv = read_distance_matrix_from_csv(file_name)
d_str = [[INF if s == '' else s for s in row] for row in d_csv]
d_int = [[int(s) for s in row] for row in d_str]

for row in d_int:
    print(row)
# [0, 10, 100000, 100000, 100000]
# [10, 0, 8, 21, 100000]
# [100000, 8, 0, 100000, 100000]
# [100000, 21, 100000, 0, 16]
# [100000, 100000, 100000, 16, 0]

result = warshall_floyd(d_int)

for row in result:
    print(row)
# [0, 10, 18, 31, 47]
# [10, 0, 8, 21, 37]
# [18, 8, 0, 29, 45]
# [31, 21, 29, 0, 16]
# [47, 37, 45, 16, 0]

（追記）
結果を CSV ファイルに保存するコードを追記します。

なお，最初の2行はヘッダとインデックスを追加するためのものです。必要なければコメントアウト等をしてください。

result = [[i + 1 for i, _ in enumerate(result)]] + result
result = [[i if i > 0 else ''] + row for i, row in enumerate(result)]

with open('result_' + file_name, 'w', newline='') as csvfile:
    writer = csv.writer(csvfile)
    writer.writerows(result)

（追記2）
結果を CSV ファイルへ保存する部分も含めたコード全体を示します。

処理する 2000x2000 の CSV ファイルの「コピー」を作業フォルダに移動し，その名前を data_2000.csv に変更してから実行してください。

import csv

def warshall_floyd(dist):
    n = len(dist)
    for k in range(n):
        # print(k)
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

def read_distance_matrix_from_csv(filename):
    with open(filename, 'r', newline='') as csvfile:
        reader = csv.reader(csvfile)
        return [row[1:] for i, row in enumerate(reader) if i > 0]

file_name = 'data_2000.csv'
INF = '100000'

d_csv = read_distance_matrix_from_csv(file_name)
d_str = [[INF if s == '' else s for s in row] for row in d_csv]
d_int = [[int(s) for s in row] for row in d_str]

result = warshall_floyd(d_int)

with open('result_' + file_name, 'w', newline='') as csvfile:
    writer = csv.writer(csvfile)
    writer.writerows(result)

Comments

[nudru]

little_street様
ありがとうございます。
送って頂いたコードの、25〜29行目の行列がcsvファイル内の行列を入れると思うのですが、私が算出したい行列は2000×2000ほどなので、どのようにすればよろしいでしょうか。

[little_street]

実際にこのコードを使う場合には，実害はありませんが紛らわしいので25から29行目と35から39行目は削除しておいた方が良いでしょう。

2000ｘ2000 のデータが格納された CSV ファイルの名前が仮に data_2000.csv だとすると以下の設定をして実行すれば良いと思います。

file_name = 'data_2000.csv'

ただし，結果も 2000ｘ2000 になるので画面に出力せず CSV ファイルに保存した方が良いでしょう。コードを回答に追記しました。

なお，このプログラムを使う頻度が低ければ許容範囲かもしれませんが，Python のループ処理は速いとは言えません。私の環境（macOS(M1)，Python 3.11.6）で 500ｘ500 のデータで試したところ計算時間が約 13 秒かかったので，2000ｘ2000 なら（3重ループなので 4ｘ4ｘ4 =）64 倍の 800 秒以上かかる計算になります。

[nudru]

ありがとうございます。
csvファイルとして読み取れればいいため、23〜29,33〜39は無視しました。
31行目を打ち、改行したときに>>>が出ず、文字が打てなかったためここも無視さしたのですがよろしいでしょうか？
また、これで進め、送って頂いた2つ目のコードの1,2行目は無視し、それ以降はそのままコピペすると、以下のようなエラーが出たのですがどのようにすればよろしいでしょうか。
16行目の時にファイルのことでエラーが出なかったので、なぜここでエラーが起きたのかわかりません。

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OSError: [Errno 22] Invalid argument: 'csvファイルのパス'

[nudru]

下のURLに実際のcsvファイルを載せているので、していただけないでしょうか。
https://www.socialsim.kke.co.jp/forum/gis-cad-dataconverter/____a

[little_street]

とりあえず，回答にコード全体を追記（追記2）しました。

[nudru]

ありがとうございます。
idleでやったのですが、
コードを書く前の上の部分の
Python 3.11.6 (tags/v3.11.6:8b6ee5b, Oct 2 2023, 14:57:12) [MSC v.1935 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.

で、最初の方の8b6ee5bの8が赤くなり、syntaxerror、invalid decimal literalとなりました。

[little_street]

idle は（ほとんど使ったことがないですが）今回のようなケースでは以下の手順でしょうか。

* data_2000.csv を準備したフォルダで idle を起動

* File > New File でエディタを起動

* （追記2）のコードをコピー（右上[+]）し，エディタ画面に貼り付け
※ 6行目のコメント（# ）をはずしておくと進行（0 -> 1983）がわかりやすい

* File > Save as... で適当な名前を付けて保存

* Run > Run Module で実行すると，IDLE Shell 画面で処理が進行（0 -> 1983）