左上から右下のセルまでの最小パス。北、南、東、西の方向に移動することができます

Question

2次元マトリックスの左上から右下のセルまでの最小パスの検索方法北、南、東、西の方向。

Answer 1

コスト値が非負に制限されている場合、問題はDijkstra's最短経路アルゴリズムによって解決できます。それ以外の場合は、負の長さのサイクルが発生するため、問題は明確に定義されていません。より具体的には、セルAからBまでの辺の重みは、Aの重みとなるように設定される。右下隅の端末セルの重みがすべてのパスに含まれます。