Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

Graph

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

EDIT: we have adjacency List.

share|improve this question
    
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
add comment

5 Answers 5

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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/

share|improve this answer
    
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
add comment

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?

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
4  
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
add comment

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)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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