CareerCup

Not enough information in the question. What is the weight of the extra node? Why don't just add extra edge between X and Y?

How is the graph represented?

Do a DFS on the weighted graph, and get the min. weight to reach Y from X. Now return min(DFS weight, W).
Either reach the destination through creating an edge of weight W(if there is none) or some other way traversing the graph. There is no point in creating another edge at someplace in the graph since it will always be greater than W.

Cannot you just apply dijkstra and select the shortest path?

Take the graph:

-----------------[3000]---
 /                                    \
1---[10000]---2-----[1]-----6
 \
  ----[5]----3
  \
   ---[2]----5

If source = 1, target = 6, and w = 15, the best path is by going to node 5 and then creating an edge from 5 to 6.

So, essentially, we have to do the following:
1. Find the shortest path from source to all other nodes, and let s2t be the shortest path from source to target
2. If s2t does not exist, return w (as we can introduce a new edge of weight w between source to target)
3. If s2t >= w and no direct edge exists between source and target, return w (as we can introduce a new edge of weight w between source to target which will be better than the current shortest path through some other nodes)
4. Let maxAllowedDistance = s2t - w;
5. Using the original distances list, find the node with the minimum distance such that the node does not a direct edge to target and whose distance is less than maxAllowedDistance. Let the distance of that node be D1min
5. Find the shortest path from target to all other nodes. From among these distances, find the node with the minimum distance such that the node does not have a direct edge to source and whose distance is less than maxAllowedDistance. Let the distance of that node be D2min
6. If D1min and D2min exist, return min(D1min, D2min) + w
7. If D1min exists, return D1min + w
8. If D2min exists, return D2min + w
9. return s2t (no addition of edge with weight w possible)

Steps 5 to 8 essentially try to find an alternate route to target (or source) which is cheaper than the original route even after addition of an edge of weight w

if the weights are only positive then it is easy. If the start node doesn't have direct edge to end node, then answer is 0. Otherwise find first shortest path by dijkstra. Then, find the nearest node to start that isn't connected directly with the end node and add extra edge of weight 0.
If the weights can be negative. Firstly we have to replace dijkstra with cruskal(MST) or just adjust weights to be relative to the smalles weight in the graph.

public class UnDirectedGraphMinWeight {

static class Node {
private Map<Node, Integer> mAdjacencyWeight = new HashMap<>();

public void add(Node node, int weight) {
mAdjacencyWeight.put(node, weight);
}

private int findMinWeight(Node B) {

if (mAdjacencyWeight.size() == 0) return 0;

if (mAdjacencyWeight.containsKey(B)) {
return mAdjacencyWeight.get(B);
}

int minWeight = Integer.MAX_VALUE;

for (Map.Entry entry : mAdjacencyWeight.entrySet()) {
int weight = ((Node) entry.getKey()).findMinWeight(B);
if (weight > 0)
minWeight = Math.min(minWeight,
(Integer) entry.getValue() + weight);
}

return minWeight;
}
}

public static void main(String[] args) {

Node A = new Node();

Node B = new Node();

Node C = new Node();

Node D = new Node();

Node E = new Node();

Node F = new Node();

A.add(B, 5);
A.add(C, 3);

B.add(D, 10);
B.add(E, 7);

E.add(F, 7);
E.add(D, 7);

System.out.println(A.findMinWeight(F));
}
}

{
public class UnDirectedGraphMinWeight {

    static class Node {
        private Map<Node, Integer> mAdjacencyWeight = new HashMap<>();

        public void add(Node node, int weight) {
            mAdjacencyWeight.put(node, weight);
        }

        private int findMinWeight(Node B) {

            if (mAdjacencyWeight.size() == 0) return 0;

            if (mAdjacencyWeight.containsKey(B)) {
                return mAdjacencyWeight.get(B);
            }

            int minWeight = Integer.MAX_VALUE;

            for (Map.Entry entry : mAdjacencyWeight.entrySet()) {
                int weight = ((Node) entry.getKey()).findMinWeight(B);
                if (weight > 0)
                    minWeight = Math.min(minWeight,
                            (Integer) entry.getValue() + weight);
            }

            return minWeight;
        }
    }

    public static void main(String[] args) {

        Node A = new Node();

        Node B = new Node();

        Node C = new Node();

        Node D = new Node();

        Node E = new Node();

        Node F = new Node();

        A.add(B, 5);
        A.add(C, 3);

        B.add(D, 10);
        B.add(E, 7);

        E.add(F, 7);
        E.add(D, 7);

        System.out.println(A.findMinWeight(F));
    }
}

}