Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
413 kez görüntülendi
Girdi : n×n agirlik matrisi A

          Ai,j degeri i kosesi ile j kosesinin arasinda baglanti varsa baglantinin agirligi, yok ise 0

Cikti : n×n  en kisa uzaklik tablosu D

 

Kisaca size agirliklari olan bir cizge verecegiz ve sizden her koseden her koseye olan en kisa uzakligi istiyoruz
Veri Bilimi kategorisinde (1.6k puan) tarafından  | 413 kez görüntülendi

2 Cevaplar

0 beğenilme 0 beğenilmeme
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=(0530050350330400540300030)

 

distanceMatrix=(053710503583304775403108730)

(2.9k puan) tarafından 
0 beğenilme 0 beğenilmeme

Aslinda bu soruyu matriks carpimi ile cozebiliriz. 

Su Halkamsi da calisacagiz

(R{},min,+,,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  mn=n adimda varabilecegimiz koselere olan en kisa uzaklik. Eger m, k×k bir matriks ise, mk 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 

(1.6k puan) tarafından 
20,288 soru
21,830 cevap
73,517 yorum
2,612,994 kullanıcı