矩陣中的最短路徑

Question

我想爲NXN MATRIX（如下面的3X3矩陣）找到最短路徑。起始於第1列的任一行和列在下面3中的矩陣A的最短路徑是1，3,2的任一行結束時，4.

A = [1 3 9; 
    4 2 4; 
    5 4 9]; 

Answer 1

的標準方法是給第一代表你的問題，因爲一張圖。在你的情況下，如果你將矩陣中的每個單元看作一個頂點，那麼從頂點到右邊的單元格，上面的單元格和下面的單元格（它們中的任何一個可能不存在，因爲它們脫落矩陣的邊緣）。回溯到前一列無法爲最短路徑做出貢獻，因此我們不包含這些邊緣。如果你確實包括了它們，答案也會相同，但可能會延長一小部分。

使用索引編號，那麼，我們有以下的邊緣和重量：

i j s 
[1,2]=4 
[1,4]=3 
[2,1]=1 
[2,3]=5 
[2,5]=2 
[3,2]=4 
[3,6]=4 
[4,5]=2 
[4,7]=9 
[5,4]=3 
[5,6]=4 
[5,8]=4 
[6,5]=2 
[6,9]=9 
[7,8]=4 
[8,7]=9 
[8,9]=9 
[9,8]=4 

（標籤i，j和s的下面使用。）但是，這並不佔移動的初始成本第一列，所以我們添加具有邊到每個這些節點的一個新節點：

i j s 
[10,1]=1 
[10,2]=4 
[10,3]=3 

不幸的是，我還沒有發現這樣的一個聰明的方法，但它是非常簡單，一旦你完成後，您需要使用以下3個列向量來創建稀疏矩陣：

S = sparse(i,j,s,m,n,nzmax) 

其中

i,j,s are column vectors as labeled from the edge/weight list above 
m = n = numel(A)+1 
nzmax = numel(i) = numel(j) = numel(s) 

從那裏，你會用Dijkstra's Algorithm來找到新節點10開始單源最短路徑。您的答案將是最右邊一列（節點7,8或9，在這種情況下）的節點具有最小的路徑距離。

如果您有生物信息學工具箱，可以使用shortestpath。如果你不這樣做，在File Exchange上有幾個Dijkstra的實現。