CODEWITHSUNDEEP
algorithmgraph-theory
MrDatabase
MrDatabase

Reputation: 44425

How to efficiently construct a connected graph?

For fun I'm learning about graph theory and I came across this problem. Given a set of vertices V, a set of edges E, and a weight for each edge in E, how can I efficiently construct a graph G such that:

The edges in E are directed, when all edges in E are present there can be cycles.

Upvotes: 2

Views: 2653

Answers (4)

Faran Shabbir
Faran Shabbir

Reputation: 423

ok... can i know what MrDatabase is after? SSSP algorithms (dijkstra, Bellman-Ford) are variation of MST, which ars just mentioned. Dijkstra does not solve negative weight cycle issue while Bellman-Ford does.

Upvotes: 2

John Fouhy
John Fouhy

Reputation: 42183

To add to ars's answer, if your graph contains edges with negative weight, then the problem becomes more difficult (and there may be no solution if you have a negative-weight cycle).

Upvotes: 1

Faran Shabbir
Faran Shabbir

Reputation: 423

Read Bellman-Ford Algorithm. It supports negative weight cycles. Dijkstra's algorithm is more efficient but it doesn't support negative weight cycles.

Upvotes: 0

ars
ars

Reputation: 123468

See Minimum Spanning Tree algorithms.

Upvotes: 3

Related Questions