Identifying Smallest Element in Each Row of a Matrix

[omario]

I have this "cost matrix" in R that represents the "cost" of going from any location to any other location (for a total of 5 locations):

X<-matrix(rnorm(25) , nrow = 5)

rownames(X) <- colnames(X) <- c("Location 1", "Location 2", "Location 3", "Location 4", "Location 5")

               Location 1  Location 2  Location 3 Location 4 Location 5
Location 1  0.4501251  2.30029903 -0.26950735  0.1723589  0.5045694
Location 2  1.1208198  1.38557818  0.25250596 -0.6174514 -0.5324785
Location 3  0.4181011  0.01103208  0.83713132 -0.7649082 -0.5619196
Location 4  0.9372365 -1.04258420  0.08397031  0.1611555  1.8356483
Location 5  1.0201278 -0.56020913  1.14815210  1.0362332 -2.2052776

I would like to find out the "Greedy Shortest Path" that starts from "Location 1" and ends at "Location 1" while visiting each location exactly once.

I think this would look something like this (R getting the minimum value for each row in a matrix, and returning the row and column name) - this code returns the smallest value in each row of the matrix:

result <- t(sapply(seq(nrow(X)), function(i) {
  j <- which.min(X[i,])
  c(paste(rownames(X)[i], colnames(X)[j], sep='/'), X[i,j])
}))

When I look at the results:

print(result)


     [,1]                    [,2]                
[1,] "Location 1/Location 3" "-0.269507349140081"
[2,] "Location 2/Location 4" "-0.617451368699149"
[3,] "Location 3/Location 4" "-0.764908186347014"
[4,] "Location 4/Location 2" "-1.04258420123991" 
[5,] "Location 5/Location 5" "-2.20527763537575" 

I think this is telling me that the "Greedy Shortest Path" (starting from "Location 1") is : 1 to 3, 3 to 4, 4 to 2, 2 to 4 ... but then I get stuck in a "2 to 4, 4 to 2" loop for ever.

• Can someone please show me how I can find the "Greedy Shortest Path" that starts from "Location 1"?

By doing this manually:

• Starting at Location 1, the "shortest greedy path" is to Location 4
• From Location 4, the "shortest greedy path" is to Location 3
• From Location 3, the "shortest greedy path" is to Location 5
• From Location 5, the "shortest greedy path" is to Location 2 (since we have already been to Location 3 and Location 4, and we can not re-visit the current Location i.e. Location 5, and can not visit Location 1 since there is still a Location we haven't visited)
• From Location 2, we now have no choice but to return to Location 1 and finish the journey

I would look to produce the following output:

Path : (1,4), (4,3), (3,5), (5,2), (2,1)
Total Distance = -0.8441315 + (-0.7244259) + (-0.3775706) + 0.3796208 + 0.3015059 =  -1.265001

• Could someone please show me how to modify my code to get this final output?

Thank you!

Note: In my real data, all diagonal elements of the Matrix are 0

[FJCC]

I think this produces something close to what you want. I used letter names for the locations because I think that is clearer.

set.seed(144)
MAT <- matrix(runif(25), nrow = 5)
dimnames(MAT) <- list(Start = LETTERS[1:5], END = LETTERS[1:5])
MAT
#>      END
#> Start          A          B         C          D          E
#>     A 0.04941462 0.63862147 0.5631212 0.05401925 0.27831223
#>     B 0.70694608 0.03611917 0.1792212 0.55869724 0.02819135
#>     C 0.72668264 0.72845970 0.5516243 0.52725605 0.59602127
#>     D 0.50099064 0.07764079 0.1459074 0.83625296 0.57009959
#>     E 0.31779135 0.82208893 0.1045274 0.38200664 0.32870787

INIT <- 1
PathEnd <- vector("character", 5)
tmp <- MAT
for(i in 1:3){
  tmp <- tmp[,-INIT] #Can't end where you started
  RowErase <- INIT
  INIT <- which.min(tmp[INIT,])
  PathEnd[i] <- names(INIT)
  tmp <- tmp[-RowErase, ] #can't repeat a start position & keep matrix square
}
NMs <- dimnames(MAT)[[2]][2:5]
PathEnd[4] <- NMs[!NMs %in% PathEnd]#penultimate step to last non-A destination
PathEnd[5] <- "A" #End at A
PathStart <- c("A", PathEnd[1:4])
Distance <- diag(MAT[PathStart, PathEnd])
names(Distance) <- paste(PathStart, PathEnd, sep = "-")
Distance
#>        A-D        D-B        B-E        E-C        C-A 
#> 0.05401925 0.07764079 0.02819135 0.10452739 0.72668264
sum(Distance)
#> [1] 0.9910614

#Display MAT to see if the path makes sense
MAT
#>      END
#> Start          A          B         C          D          E
#>     A 0.04941462 0.63862147 0.5631212 0.05401925 0.27831223
#>     B 0.70694608 0.03611917 0.1792212 0.55869724 0.02819135
#>     C 0.72668264 0.72845970 0.5516243 0.52725605 0.59602127
#>     D 0.50099064 0.07764079 0.1459074 0.83625296 0.57009959
#>     E 0.31779135 0.82208893 0.1045274 0.38200664 0.32870787

^{Created on 2022-03-30 by the reprex package (v2.0.1)}