need hint on graph theory

[ashishyadav]

i have a problem in which we have to find the farthest node from a particular node in a weighted directed graph.But starting node is changing on each query and some node may be added to graph on any given node.
Thanks in advance!!!

[tpb]

Given a starting vertex you want to find the vertex that has the longest shortest path. So find the shortest path to every vertex and pick the longest one. I'm not sure what the starting vertex and graph structure changing have to do with it. Are you supposed to preprocess the graph to optimize the algorithm?

[Ganado]

Is the graph acyclic ("DAG")? Finding the longest path is NP-Hard for a general graph (still possible, of course), but if your graph is acycilc (no cycles) then it's a lot easier.

Look into the Bellman-Ford algorithm for a general graph.
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

The Bellman-Ford algorithm will calculate the shortest paths from a given node to all other nodes. Then, you need to choose the max value/node from that list.

See also: https://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

Or are you saying that the graph is dynamically changing as you try to run an algorithm on it? At that point, anything is fair game, and your concerns are quite broad.

[dhayden]

I think the OP is saying that there are multiple queries. Each query specifies a starting node and you have to print out the node that is most distant from that one. To complicate things, before each query, a new node can be added to the graph.

Kashish, is my description right? Also, please explain exactly what you mean by "farthest path." We're assuming that you mean "the node whose shortest path is largest," but maybe you mean "the node whose longest path is largest."

Since the starting node differs for each query and you're adding a new node, my first suggestion is to use Djikstra's algorithm to find the shortest paths on each query. The question then becomes "can you optimize the solution, knowing that you already solved it for the previous query?"

[jonnin]

You may be able to keep a structure of known info (sadly you either need a complex update or do-over if the graph changes) to avoid re-doing work and speed up your algorithms. You may even be able to build your graph structure in such a way that it can automatically track the chains, and just hand you the length, if you really dig in. Not sure. A lot of these types of problems can be short circuited like this, and others can't, and still others are just moving the work around (pay up front on insert for a fast answer vs wait for answer). If these graphs can get big, you may also want to find a way to thread the above ideas to do 4 or 8 or whatever at a time.

[zyan1zyan]

this is the full question, help to do this task-:

You are given a directed graph with 'n' nodes numbered 'i' from to 'n-1'. For every 'i' from '1' to 'n-1', there is an edge from node 'i' to node 'i+1' of weight 'wi', and there is an edge from node 'n' to node '1' of weight 'wn'. Thus, the 'n' nodes form a directed cycle.

You have to process 'm' queries of the following four types. In the following, 'x' denotes a node between '1' and 'n'. Also, some queries will attempt to add or delete nodes, but it's guaranteed that the original 'n' nodes will never be deleted.

. 1 x w : Let the farthest node from 'x' be 'y'. Add an edge of weight 'w' from 'y' to a new node.
. 2 x w : Add an edge of weight 'w' from 'x' to a new node.
. 3 x : Let the farthest node from 'x' be 'y'. Delete node 'y'.
. 4 x : Let the farthest node from 'x' be 'y'. Print the distance from 'x' to 'y'.

The distance from 'x' to 'y' is defined as the shortest total weight of any path from 'x' to 'y'. The farthest node from 'x' is the node 'y' with the largest distance from 'x'.

Note: If multiple nodes are farthest from 'x', choose the one that was added to the graph most recently.

Complete the function cyclicalQueries which takes in an integer array 'w' denoting the weights of the initial edges and an integer 'm' and returns a list of answers to queries of type '4'. You have to take the query information from standard input, as described in the input format section.

Input Format:-

The first line contains a single integer 'n'.

The next line contains 'n' space-separated integers 'w1','w2',...,'wn'.

The next line contains a single integer 'm' denoting the number of queries. 'm' lines follow, where the 'ith' line denotes the 'ith' query, each in the format described above.

Constraints

- 1 <= n,w <= pow(10,5)
- 1 <= w,wi <= pow(10,9)
- 1 <= x <= n

Output Format-:

For each query of type '4', print the answer in a single line.

Sample Input 0

5
1 1 1 1 1
4
1 1 5
4 2
3 2
4 2

Sample Output 0

8
4


Explanation 0

Query 1: A new node '6' is added from node '5', with an edge weight of '5'.
Query 2: Distance from node '2' to node '6' is printed.
Query 3: Node '6' is deleted.
Query 4: Distance from node '2' to node '5' is printed.


// Complete the cyclicalQueries function below.

vector<long> cyclicalQueries(vector<long> w, int m) {
// Return the list of answers to all queries of type 4. Take the query information from standard input.

}

[dhayden]

it's guaranteed that the original 'n' nodes will never be deleted.

This makes the problem easier.

-1 <= n,w <= pow(10,5)
- 1 <= w,wi <= pow(10,9)

Negative weights make the problem much harder. You should verify if weights can be negative. Also I don't understand why this specifies "w" as having two upper limits. That makes me nervous. Is the spec unclear? Am I just not understanding something?

You can't delete any of the original N nodes. And when you add a new node, it springs forth as a branch from an existing node. So there is only 1 cycle in the graph (the original one)

- 1 <= x <= n

x can be -1? What the heck does that mean?? Aren't the original N nodes labeled 1 to N? Or are they 0 to N-1? Your description says they are "numbered 'i' from to 'n-1'" numbered from what to n-1? You should verify these details.

Okay, the point here is that it looks like the source node X is always one of the original N nodes. So if the furthest node is on a tree that sprung out of one of the original N nodes then the path must still go through the base of the tree. For each node on the cycle, store (among other things)
unsigned furthestNodeOnTree; // ID of the furthest node on the tree
int costToFurthestOnTree; // the cost from this node to furthestNodeOnTree

Now you can find the furthest node from X like so (pseudocode):

vector<Node> nodes;
unsigned lastNode = X;
int distance = 0;  // distance from X to current node on the cycle
for (i=0; i<n-1; ++i) {  // for the n-1 other nodes on the cycle;
    int nextNode = (X+i) % n +1;
    distance += weight(lastNode, nextNode);  // weight of edge from lastNode to nextNode
                    // you might chose to store these in a vector or something.
    if (distance > maxDist) {
        bestNode = nextNode;
        maxDist = distance;
   }
    if (distance + nodes[nextNode].costToFurthestOnTree > maxDist) {
        bestNode = nextNode;
        maxDist = distance+nodes[nextNode].costToFurthestNodeOnTree;
   }
   lastNode = nextNode;
}
// Now bestNode contains the number of the node on the cycle that is the base of the tree with the most distant node. 

Note that bestNode doesn't actually refer to the most distant node. It refers to the node on the cycle that is the root of the tree that contains the most distant node. I did this because you'll need to update this info in this node when adding or deleting other nodes. The node that is most distant is easily accessible as nodes[bestNode].furthestNodeOnTree.

When you insert or delete a node, you just have to update the max distance/node for the node on the cycle that is the base of the tree.

[zyan1zyan]

none of the value is negative , it's not the minus sign , it's a hyphen(-) sign.

[zyan1zyan]

@dhayden
i have sent my code to you on PM , please see and debug it
and make my code correct.

[closed account 1TD80pDG]

@zyan1zyan. Pm me i can debug your code