すべての質問
2 件の質問
1
票
1
回答
453
閲覧数
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
0
票
2
回答
534
閲覧数
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=2」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。
グラフ部分はコードのrouteにあたります。
出力
$ python dijkstra.py
visited to A.
...