-2

Anyone knows this?

A looped tree is a weighted, directed graph built from a binary tree by adding an edge from every leaf back to the root. Every edge has a non-negative weight.

  1. How much time would Dijkstra’s algorithm require to compute the shortest path between two vertices u and v in a looped tree with n nodes?
  2. Describe and analyze a faster algorithm.
tobias_k
  • 81,265
  • 12
  • 120
  • 179
Hawks
  • 11
  • 1

2 Answers2

2

How much time would Dijkstra’s algorithm require to compute the shortest path between two vertices u and v in a looped tree with n nodes?

It will take O(VlogV) time (worst case analysis).
Note that there is a single simple path for each pair of nodes (u,v) that connects u to v. If this path for some reason contains a very heavy weighted edge, Dijksta's algorithm is going to keep postponing taking this edge, and will fail to discover the correct route until it will, which will make the algorithm have to discover most of the vertices in the looped tree, making the complexity O(VlogV) (Note that E is in O(V) for this graph).

Describe and analyze a faster algorithm.

Since there is a single simple path, you just need to find it.
It can be easily done by finding the lowest common ancestor in the tree (without loops), and then finding a route to this ancestor from u.
Complexity of this algorithm is O(h) - where h is the height of the graph.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
0

I think the answer by amit is wrong.

In Describing and analyze a faster algorithm.

you can't find the cheapest route from vertex u to this ancestor in O(h), therefore, this algorithm is not O(h). For 2 reasons, if internal nodes only have parent to child directed edge, we need to look down from u to find the cheapest route to common ancestor (or the root), and I am not aware of an algorithm that can do that. Second reason, if there are parent->child and child->parent edges, then the path from source vertex to lowest common ancestor vertex can be through any of the 3 adjacent vertex of any internal tree nodes( vertex) or 1 adjacent vertex(root) of any leaf node vertex, thus we can't do it in O(h).

Based on my understanding of the problem, child->parent edge is not in the definition of looped-tree graph. Therefore, the only we is to go down the tree and come back at the top and from root to target is a simple single path. Therefore, we reduce the problem to finding the cheapest route from u to root, thereby reduce the complexity.

Further, if target is a direct descendant of source, we will stop the during finding the cheapest route to root. if source is the root, the problem is trivial since the route is the simple single path from root to target by going down the subtrees of target.

Frank Liu
  • 1