Prim's algorithm for weighted directed graph

0
votes

I am learning minimum spanning tree. I go through Prim's algorithm for weighted directed graph.

Algorithm is simple

  • you have two set of vertices, visited and non-visited
  • set distance for all edges to infinity
  • start with any vertex in non-visited set and explore its edges
  • In all edges, update distance of the destination vertex with the weight of the edge if destination vertex it is not visited and if weight of the edge is less than the distance of destination vertex
  • pick the non-visited vertex with smallest distance and do it again until all vertex are visited

I believe with above algorithm, I will be able to find the spanning tree having minimum cost among all spanning trees, i.e. Minimum spanning tree.

But I applied it to the following example and I think it is failed.

Consider following example

Vertices are {v1,v2,v3,v4,v5} and edges with weight
(x,y) : w =>
(v1,v2) : 8
(v1,v3) : 15
(v1,v4) : 7
(v2,v5) : 4
(v4,v5) : 7

First I explore v1, it has edges to v2,v3,v4 so graph become
Vertex v1 is visited and (vertex, distance) =>
(v2,8)
(v3,15)
(v4,7)

Now v4 has the least distance i.e. 7 so I explore v4, it has edge to v5 so following modification occur
Vertex v4 is visited and (vertex, distance) => (v5,7)

Now among all v5 is having the least distance , i.e. 7 , so I explore v5 and it does not have any edge so I just mark it visited

Vertex v5 is visited

Now, confusion starts from here

The vertex with the least distance is now v2, it has edge to v5 with the weight 4 and currently v5 having distance is 7, previously assigned by the edge (v4,v5) : 7 , so, I believe that to make minimum spanning tree, distance for v5 should be updated from 7 to 4 as 4 < 7 but it will not because v5 has already been visited and Prim's Algorithm do not update the distance of the vertex that already been visited and distance for v5 will remain 7 instead of 4 and this tree will not have minimum cost

Do I get it right ? or am I doing any mistake ?

Thanks

1
algorithmgraphminimum-spanning-treeprims-algorithm
What you describe is in fact Prim's algorithm, but it works only for undirected graphs. Quoting Wikipedia on the directed version: "For directed graphs, the minimum spanning tree problem is called the Arborescence problem and can be solved in quadratic time using the Chu–Liu/Edmonds algorithm". – Gassa
it can even be solved in m + n log n, just like Prim – Niklas B.

1 Answers

4
votes

First I should mention that Prim's algorithm is just applicable to undirected graphs so if we consider the graph is undirected, this is the step by step progress of the algorithm on your case:

enter image description here

And you should consider that finding a minimum spanning tree is not even possible many times in the directed graphs, nevertheless the closest notion to MST for directed graphs is minimum cost arborescence.