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.
 A: 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/
A: 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?
A: 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: If you're interested in distances between all pairs of vertices, then perhaps you want to take a look at Warshall's Algorithm.
A: 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) 
