1
$\begingroup$

I have an undirected graph, where some edges are considered to be "bad" edges, and I want to determine whether or not every two nodes are connected by a path that contains at most one bad edge. Is there a name for this problem? Otherwise, what are some hints for an algorithm to approach this? I've thought about using Djikstra's, with bad edges having weight 1, but there is the problem of figuring out from which node to start.

$\endgroup$
1
$\begingroup$

You vision of using Dijkstra's algorithm is neigther bad nor perfect. You may compute distance from vertex $v \in V(G)$ to all vertices $u \in V(G)$. Taking each possible $v$ you consider all pairs of vertices and use $\Theta(nm \log n)$ time (if you implement Dijkstra's algoirthm on binary heap), where $n$ is the number of vertices and $m$ is the number of edges. (I suppose graph to be connected (that implies $m \ge n - 1$) to eliminate some summands.) In many cases it would be better than Fabio Somenzi has suggested, because Floyd–Warshall algorithm takes $\Theta(n^3)$ time.

But we can look deeper. You can compute distance from vertex $v \in V(G)$ to all vertices $u \in V(G)$ using one BFS with deque if all weights are 0 or 1 (your case). This gives $\Theta(nm)$ time. However it is sill far from perfect solution.

Let us completely deny bad edges. We can find all connected components in reduced graph using BFS or DFS in $\Theta(n + m)$ time. We can walk inside any component without bad edges. Now the problem is to get from one such to another using at most one bad edge. This means that each component should be directly connected to each other by a bad edge. So all we need just to contract each good edge of initial graph and check new graph (with bad edges only) for being complete. This approach can be done in $\Theta(n + m)$ of total time that is the best possible.

$\endgroup$
1
$\begingroup$

If I understand what you ask, you need an all-pair shortest path algorithm, like Floyd-Warshall. As you already figured out, give the bad edges a weight of one, and the remaining edges a weight of zero, and check that the distance matrix is all zeros and ones.

$\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.