非ユークリッド距離（Matlabの）

Question

私は（3×4）に接続し、 "1"（コネクティビティ4 "北、南、東、西"）のM行列を持っているが、言う：

M=[0 1 1 1; 
    1 1 0 1; 
    0 1 0 1]; 

インデックス要素：idx = 2 4 5 6 7 10 11 12; （8要素）。 Mは白黒ピクセルのマトリックスとして見ることができる。

ホワイトピクセル分離の（8x8）Dマトリックスを解決するためのアイデアはありますか？ （[説明]：IDX = 2と12との要素は5つの白画素によって分離離れ6つの手順=である）

D=[0 2 1 2 3 4 5 6; 
    2 0 1 2 3 4 5 6; 
    1 1 0 1 2 3 4 5; 
    2 2 1 0 1 2 3 4; 
    3 3 2 1 0 1 2 3; 
    4 4 3 2 1 0 1 2; 
    5 5 4 3 2 1 0 1; 
    6 6 5 4 3 2 1 0] 

Answer 1

は、ノードが非ゼロ要素でグラフを作成し、エッジが隣接要素を接続します。隣接リストあなたの例のために（接続するエッジのリスト）：

2-5 
4-7, 4-5 
5-2, 5-4, 5-6 
6-5 
and so on 

そして全てのノード間のすべての最短経路を見つけるために、任意のアルゴリズムを使用します。

Breadth-first searchは、最初のノードから次に2番目のノードからの最短パスをすべて見つけることができます。複雑さO（V * E）。ここでE〜Vなので、O（V^2）

Floyd-Warshall algorithmはかなりシンプルです - 3-4コード行です。 O（V^3） - 重み付きグラフを対象としています。