Timeline for Solution to the sum of k-step path lengths between node pairs in directed weighted graphs
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2021 at 9:46 | vote | accept | chrisLoweDev | ||
| Oct 1, 2021 at 7:46 | comment | added | caduk | yes, that's correct | |
| Oct 1, 2021 at 7:36 | comment | added | chrisLoweDev | Sorry @caduk, my confusion is more related to the structure of the matrix A. From your answer, my understanding is that it is a matrix of size N x N, in which each element is a 2 element vector, the first being n and the second, s. Is that correct? And then I can square that matrix using the regular matrix multiplication or exponentiation operations? TIA | |
| Sep 30, 2021 at 19:32 | comment | added | caduk | For matrix exponentiation, you can use the squaring by exponentiation, which takes only $log(n)$ multiplication of matrices, but good libraries should provide also this functionality. All in all, the complexity is $n^3log(n)$ with naive matrix multiplication, and becomes $n^{\omega}log(n)$ with $\omega$ a better exponent using for example the Strassen algorithm. | |
| Sep 30, 2021 at 19:29 | comment | added | caduk | For matrix multiplication, you can go with a naive implementation in $n^3$, but almost all algorithmic results of matrix multiplication are generic enough to work with elements of a ring (here, you even have a field, because the multiplication is invertible), so you can use the powerful machinery of matrix theory. Many libraries of linear algebra have an efficient generic implementation of matrix implementation, like BLAS. You can implement such a specialization very easily in Julia using LinearAlgebra.jl. or in python using Numpy. | |
| Sep 30, 2021 at 16:24 | comment | added | chrisLoweDev | Hi @caduk, thanks so much for updating, it's a lot clearer now and have no problem following up to, and including, the equation following "...recurrence is given by:". I'm still unsure about how I'd actually implement this and if there's a way to do so other than calculate element-by-element. I'm assuming there is a way to achieve the result using a matrix-wide operation, given what you have suggested elsewhere, but I'm not sure of what that would look like. Any further help would be much appreciated. | |
| Sep 28, 2021 at 11:34 | history | edited | caduk | CC BY-SA 4.0 | clarfying |
| Sep 28, 2021 at 10:56 | comment | added | caduk | Yes, this is a similar construct as the min-plus matrix multiplication, but with a recurrence relation adapted to the problem. I will try to clarify the recurrence. | |
| Sep 28, 2021 at 10:14 | comment | added | chrisLoweDev | Thanks @caduk for the answer. I don't fully understand what you're proposing unfortunately, are you able to clarify any further and/or offer an example? Also, are the multiplication and addition functions displayed as they are to represent max-plus algebra, or matrix algebra more generally? | |
| Sep 23, 2021 at 11:13 | history | edited | caduk | CC BY-SA 4.0 | added 74 characters in body |
| Sep 23, 2021 at 11:13 | comment | added | caduk | Yes, this is important to note, I edited. | |
| Sep 23, 2021 at 10:07 | comment | added | Peter Taylor | Note that this requires non-edges to be represented by $(0, 0)$ instead of $(0, \infty)$. | |
| S Sep 23, 2021 at 9:53 | review | First answers | |||
| Sep 23, 2021 at 11:23 | |||||
| S Sep 23, 2021 at 9:53 | history | edited | caduk | CC BY-SA 4.0 | added 19 characters in body |
| Sep 23, 2021 at 9:49 | comment | added | caduk | You just need to compute $A^k_{i,j}$, using exponentiation by squaring for efficiency. | |
| Sep 23, 2021 at 9:40 | comment | added | CommunityBot | As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. | |
| Sep 23, 2021 at 9:39 | comment | added | Alex M. | But how does this answer the question? | |
| S Sep 23, 2021 at 9:05 | review | First answers | |||
| Sep 23, 2021 at 9:40 | |||||
| S Sep 23, 2021 at 9:05 | history | answered | caduk | CC BY-SA 4.0 |