I am currently writing up some notes on the max-plus algebra $\mathbb{R}\_{\max}$ (for those that have never seen the term "max-plus algebra", it is just $\mathbb{R}$ with addition replaced by $\max$ and multiplication replaced by addition. For some reason, authors whose main interest is control-theoretic applications never seem to use the term "tropical", and I have been reading from such authors). There is a nice result which says the following: 


$\textbf{Theorem.}$ Let $G$ be a directed graph on $n$ vertices such that each arc $(i,j)$ in $G$ has a real weight $w(i,j)$. Define the $n \times n$ matrix $A$ by $(A)\_{ij} = w(i,j)$ if $(i,j)$ is an arc, and $(A)\_{ij} = -\infty$ otherwise. Then for each $k > 0$, the maximum weight of a path of length $k$ from vertex $i$ to vertex $j$ is given by $(A^{\otimes k})\_{ij}$ (here, $A^{\otimes k}$ is just the $k$th power of $A$, computed using the $\mathbb{R}\_{\max}$ operations).


This result is certainly analagous to the standard result that the $ij$-entry of the $k$th power of the adjacency matrix gives the number of walks of length $k$ from vertex $i$ to vertex $j$. When writing up my notes I found myself claiming that the above theorem provides some evidence that $\mathbb{R}\_{\max}$ is in fact a natural setting in which to study weighted digraphs, since there is no natural definition of an ``adjacency matrix'' of a weighted digraph (in the usual setting of $\mathbb{R}^{n \times n}$) that gives useful information about the weights. This seemed like too strong of a claim, especially since I am no expert in networks or combinatorial optimization. This leads to the question:


$\textbf{Question.}$ Is there a standard matrix (in $\mathbb{R}^{n \times n}$) associated with a weighted digraph that is analogous to the adjacency matrix and captures in a useful way the weights of the arcs?


$\textbf{Clarification:}$ By "analogous to the adjacency matrix" I mean a matrix that is defined simply in terms of the graph (vertices, arcs, and weights). I imagine there are all sorts of matrices associated to weighted digraphs so that computers can be used to analyze networks. But I am not interested in, say, a matrix that requires a complicated algorithm to compute its entries.



Is there an "adjacency matrix" for weighted directed graphs that captures the weights?
It looks like in your definition the weight of a path is the **sum** of the weights of its edges. In many combinatorial applications a natural definition of the weight of a path is the **product** of the weights of the edges, and there one uses precisely the weighted adjacency matrix $A\_{ij} = w(i, j)$ (as an element of the usual $\mathbb{R}$). This is the definition relevant to, for example, the theory of Markov chains, where $w(i, j)$ is a transition probability.


One way to get information about sums of weights is to use $B\_{ij} = e^{w(i, j)}$, but what you'll get in the end is a sum of exponentials of weights instead of (direct) information about the maximum or minimum weight. I think one can instead consider $B\_{ij}(t) = e^{t w(i, j)}$ and in the "low-temperature" limit as $t \to \infty$ this approaches the tropical result; the largest term will dominate. (I think physicists call these things partition functions.)


