Graph Theory Distance Algorithm

My own problem:

Let G be a undirected graph with $n$ vertex and $m$ edges.
We have a list that $v_{1} \rightarrow v_{2}$ but it's not important now.
Every edge has a weight equal to X.
Our task is to find all pairs $(v_i, v_j)$ that fastest path from $v_i$ to $v_j$ is about $w = 2X$.

(Look at example)

Create algorithm with $O(n^2)$ complexity, simlar or faster :)

Example:

$n = m = 5$
$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5$ and $v_1 \rightarrow v_3$

Solution:

$(1,4), (2,4), (3,5)$.

Picture:

Shortest path from $v_1$ to $v_4$ is 2X (the same with another solutions).

EDIT: we have adjacency List.

-
I doubt there is anything faster than $O(m\log m)\subseteq O(n^2\log n)$ (with $O(m)$ storage). –  Hagen von Eitzen Oct 20 '12 at 13:37
Can you tell me something about algorithm with this complexity? –  John Smith Oct 20 '12 at 19:26

In terms of the $n\times n$ adjacency matrix $A$, you are looking for all pairs $(i,j)$ such that $A_{ij}=0$ and $(A^2)_{ij}>0$ (or, equivalently, $\exists{k}:A_{ik}A_{kj}>0).$ Since there can be as many as $\Theta(n^2)$ such pairs, any algorithm to do this is going to take at least $\Omega(n^2)$, as a lower bound. Ordinary matrix multiplication, or any of the obvious graph-based approaches (e.g., start at each node and consider all pairs of its neighbors), is going to be $O(n^3)$. As a better upper bound, there are fast matrix multiplication algorithms like the Strassen algorithm or the Coppersmith-Winograd algorithm that can compute the matrix product in $O(n^{\alpha})$ for $2<\alpha<3$. Strassen has $\alpha=\log_2{7}\approx2.807$; its implementation is straightforward enough for everyday use; and it becomes superior to ordinary matrix multiplication for reasonably-sized matrices. (Coppersmith-Winograd, on the other hand, is mainly of theoretical interest.) One might expect that, since you would be satisfied with Boolean matrix multiplication (BMM) instead of actual integer matrix multiplication, there might be a faster method. Somewhat surprisingly, this doesn't seem to be the case: BMM is just as slow as more general matrix multiplication. That being the case, I believe the fastest practical algorithm for your purposes is going to be Strassen.

NB: If your matrix has additional properties, for instance if the maximal degree of any node is $O(n^\beta)$ for $\beta<1$, then you can do better. Local search is going to be $O(n^{1+2\beta})$ in that case.

-

A method, create bitmaps at every vertex, saying which vertices it is connected to. This takes $O(n^2)$ time. Then, in the second stage, for every vertex, go to its neighbors, and or, its bitmap with the ones of the neighbors. All 1s in this data-structure indicate vertices reachable within 2 distance from original vertex (Before this, one can compute the intersection of origin's bitmap and the derived bitmap of all neighbors.). Similarly do for all other vertices. This takes $O(E)$ time since sum of degrees is $O(E)$, but this is still quadratic.

This is $O(n^2)$ time and $O(n^2)$ space. If you have adjacency list (in compact bitmap representation, with either rows or columns in a bitmap), there is no additional space complexity. This takes $O(E)$ time, so ideal for sparse graphs too. Also, to avoid hash-map to remove duplicates at the end, you can use the following slight change:

• Or all the adjacent vertex adjacency lists, and or it with origin vertex's.
• If you want strictly 2 distance, then do not or with origin's adj list, do xor it with the intersection of origin bitmap, and bitmap constructed from neighbors.
• Then output all vertices corresponding to 1s there.
• To avoid duplicate outputting (like (1, 4) and (4, 1)), only include vertices which are of a greater index

Salahuddin

http://maths-on-line.blogspot.in/

-
Just to be clear, while representing the adjacency matrix in bitmap form may speed things up, it doesn't affect the time complexity. The size of the bitmap is $\Omega(n)$, and it takes time $\Omega(n)$ to find the intersection of two such bitmaps, so the overall time complexity here is still $\Omega(n^3)$. –  mjqxxxx Oct 26 '12 at 16:54

I don't know too much about the complexity of this, would it work?

If $A$ is the matrix corresponding to the graph, calculate $A^2$ and then you seek all $ij$ such that $A^2{ij} \neq 0$ and $A_{ij}=0$.

Note that if you calculate $A^2$ using if/or as the two operations (in binary), your output is exactly the set of positive entries in $A^2-A$.

P.S. You can also try this: Dijstra Algorithm yields the smallest distance spanning tree. Then in this you just do what Belgi suggested: for each vertex list all the possible pairs made by its neighbours.

P.P.S. Consider the following graph: $V={v_1,..., v_n}, E=\{ (v_1,v_i) | 2 \leq 2 \leq n \}$. This is a tree, and the outcome is $\{ (v_i, v_j)| 2 \leq i,j \leq n \}$. Can an algorithm be better than $O(n^2)$ and have an output of $\frac{(n-1)(n-2)}{2}$ elements?

-
Our graph isn't a tree. Smallest distance spanning tree wouldn't work. –  John Smith Oct 23 '12 at 18:05
I will read something about your algorithm, i will write more next day. But i think that it will be too slow :( –  John Smith Oct 23 '12 at 18:09

If you're interested in distances between all pairs of vertices, then perhaps you want to take a look at Warshall's Algorithm.

-
It's too slow. I want to find all pair of vertex which minimal distance is 2X. (the best time will be $O(n log n)$ or $O(n)$). –  John Smith Oct 18 '12 at 13:53
Do you have any better solution? –  John Smith Oct 18 '12 at 16:43
Simply the fact that you need to check pairwise distances suggests that you need at least $\mathcal{O}(n^2)$. Why are you convinced there exists a solution in $\mathcal{O}(n\log n)$ or $\mathcal{O}(n)$? –  EuYu Oct 18 '12 at 17:13
I'm searching for the best possible algorithm, because i want to use it in my project (graph theory program). As faster than better. –  John Smith Oct 18 '12 at 17:41
And what do you think about $O(n^2)$ solution? Is it possible to construct algorithm running in this time ? –  John Smith Oct 18 '12 at 18:25

Hint: Let us assume that we have adjacency List

When is $(i,j)$ is in the output ? when there is a $k$ s.t $(i,k)$ and $(k,j)$ are in $E$.

Take $v_{1}$ for instance, each one of the element in his row (all of his neighbors) is some $k$ like the above - so you have $(v_{1},v)$ in your output for every vertex in $k$ row (his neighbors).

Just do this for all $v\in V$ and not $v_{1}$ and this should give a pretty efficient solution (I did not calculate the complexity)

-
Note: If you want the $2x$ as minimal just verify there isn't an edge conncting $v_i$ and $v_j$ and that $i\neq j$ –  Belgi Oct 17 '12 at 22:09