Agirlikli Cizgede En Kisa Yollar

Question

Girdi : $ n\times n$ agirlik matrisi $A $

          $A_{i,j} $ degeri $i$ kosesi ile $j$ kosesinin arasinda baglanti varsa baglantinin agirligi, yok ise $0$

Cikti : $ n\times n$  en kisa uzaklik tablosu $D$

 

Kisaca size agirliklari olan bir cizge verecegiz ve sizden her koseden her koseye olan en kisa uzakligi istiyoruz

Answer 1

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 
   3 \[UndirectedEdge] 1, 2 \[UndirectedEdge] 4, 
   3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5}, 
  EdgeWeight -> RandomInteger[{1, 5}, 6], EdgeLabels -> "EdgeWeight", 
  VertexLabels -> "Name"]

(m = WeightedAdjacencyMatrix[g]) // MatrixForm
distanceMatrix=GraphDistanceMatrix[g] // MatrixForm // Rationalize

 

 

$m=\left(
\begin{array}{ccccc}
 0 & 5 & 3 & 0 & 0 \\
 5 & 0 & 3 & 5 & 0 \\
 3 & 3 & 0 & 4 & 0 \\
 0 & 5 & 4 & 0 & 3 \\
 0 & 0 & 0 & 3 & 0 \\
\end{array}
\right)$

 

$distanceMatrix=\left(
\begin{array}{ccccc}
 0 & 5 & 3 & 7 & 10 \\
 5 & 0 & 3 & 5 & 8 \\
 3 & 3 & 0 & 4 & 7 \\
 7 & 5 & 4 & 0 & 3 \\
 10 & 8 & 7 & 3 & 0 \\
\end{array}
\right)$

Answer 2

Aslinda bu soruyu matriks carpimi ile cozebiliriz. 

Su Halkamsi da calisacagiz

$(\mathbb{R} \cup\{\infty\},\min ,+,\infty,0)$

yeni "toplama" islemimiz $\min$, "carpma" islemimiz ise $+$.

 

Bu islem icin matriks carpimini yazalim. Bunun disinda OkkesDulgercinin cevabinda kullandigi adjacency matrisini  yeni halkamsimizda ifade edelim ve $m$ adini verelim. Gorecegiz ki  $m^n = \text{$n$ adimda varabilecegimiz koselere olan en kisa uzaklik}$. Eger $m$, $k \times k$ bir matriks ise, $m^k$ bize istedgimiz matrisi vermeli.   

julia> function minsum(x,y)
           mat = zeros(size(x)[1],size(y)[2])
           for i in 1:size(x)[1]
               for j in 1:size(y)[2]
                   m = Inf64
                   for k in 1:size(x)[2]
                       m = min(m,x[i,k]+y[k,j] )
                   end
                   mat[i,j] = m
               end
           end
           mat
       end


julia> m = [0   5   3  Inf   Inf
            5   0   3   5  Inf
            3   3   0   4  Inf
          Inf   5   4   0   3
          Inf   Inf Inf 3   0]


julia> for i ∈ 1:5
           print("m^$i is "); display(m)
           m = minsum(m,m)
       end
m^1 is 5×5 Matrix{Float64}:
  0.0   5.0   3.0  Inf   Inf
  5.0   0.0   3.0   5.0  Inf
  3.0   3.0   0.0   4.0  Inf
 Inf    5.0   4.0   0.0   3.0
 Inf   Inf   Inf    3.0   0.0
m^2 is 5×5 Matrix{Float64}:
  0.0  5.0  3.0  7.0  Inf
  5.0  0.0  3.0  5.0   8.0
  3.0  3.0  0.0  4.0   7.0
  7.0  5.0  4.0  0.0   3.0
 Inf   8.0  7.0  3.0   0.0
m^3 is 5×5 Matrix{Float64}:
  0.0  5.0  3.0  7.0  10.0
  5.0  0.0  3.0  5.0   8.0
  3.0  3.0  0.0  4.0   7.0
  7.0  5.0  4.0  0.0   3.0
 10.0  8.0  7.0  3.0   0.0
m^4 is 5×5 Matrix{Float64}:
  0.0  5.0  3.0  7.0  10.0
  5.0  0.0  3.0  5.0   8.0
  3.0  3.0  0.0  4.0   7.0
  7.0  5.0  4.0  0.0   3.0
 10.0  8.0  7.0  3.0   0.0
m^5 is 5×5 Matrix{Float64}:
  0.0  5.0  3.0  7.0  10.0
  5.0  0.0  3.0  5.0   8.0
  3.0  3.0  0.0  4.0   7.0
  7.0  5.0  4.0  0.0   3.0
 10.0  8.0  7.0  3.0   0.0

 

Burada bir suru iddia attim ortaya, Lisans Matematik icin guzel ispatlar olabilir bunlar