2
$\begingroup$

I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible to use an adjacency matrix for Bellman-Ford without increasing significant time complexity? What would be the simplest way to use my graph-generating algorithm to the Bellman-Ford algorithm? Am I required to convert my matrix into a list?

$\endgroup$
0
$\begingroup$

It is possible to use an adjacency matrix, but you will increase the runtime in most cases.

The main core of the algorithm is, that you iterate over all edges and try to relax the distance approximations. If you have an adjacency list, you can efficiently iterate over all edges in $O(|E|)$ time, and get the the worst case complexity $O(|V| \cdot |E|)$ in total.

If you however use an adjacency matrix, in most cases you cannot iterate over all edges as efficiently. You could iterate over all entries in the matrix, and check for each one if the edge exists (e.g. check if the distance stored is infinity), however that will require $O(|V|^2)$ time and therefore lead to a total complexity of $O(|V|^3)$.

If you have a dense matrix $|E| \approx |V|^2$, then this will result in the same time complexity $O(|V| \cdot |E|) = O(|V|^3)$, but if you have a sparse graph, $|E| \approx |V|$, then iterating over all edges will take significant slower and you get the complexity $O(|V|^3)$ even though with a with an adjacency list you would have the complexity $O(|V| \cdot |E|) = O(|V|^2)$.

So it would be better, to simply convert the adjacency matrix into an adjacency list, or just a simple list of all edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.