We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our task is to find shortest path (i.e minimum cost) between the start vertex and all others vertices.

I have developed an algorithm, but I would like to create something faster than adding edges to the graph (via breadth-first search) and Dijkstra's algorithm. Here are a couple examples:

Example 1 Input: For $x=3$, $y=1$

Example 1 Graph

Possible $y$ paths included:

Example 1 Graph with y

Output: cost of shortest path from start node to node $i$ (assume that from start node to start node is 0)

1: 0
2: 2
3: 2
4: 1
5: 1
6: 3

Example 2 Input: For $x=3, y=2$

Example 2 Graph


1: 0
2: 3
3: 3
4: 2
5: 5

  • $\begingroup$ I don't understand the output of your second example at all. Is there a typo? $\endgroup$ – Peter Shor Nov 2 '12 at 18:46
  • $\begingroup$ n = 5, m = 5, start vertex is 1, x = 3, y = 2. We have edges from $v_i$ to $v_j$, i will write it in pairs : $(1,2), (2,3), (3,4), (4,5), (3,1)$. So in output we have got that minimal costs to drive from start vertex ($V_1$) to $v_i$ is for $i = 1..5 : (0,3,3,2,5)$. If you have more question, please ask. $\endgroup$ – Edger Bachmann Nov 2 '12 at 19:13
  • $\begingroup$ I see ... I missed the "no direct path" in the problem statement. $\endgroup$ – Peter Shor Nov 2 '12 at 19:15
  • $\begingroup$ Are you sure you're adding the edges to the graph reasonably efficiently? You should be able to do this in time $O(E')$, where $E'$ is the number of edges in the new graph. (I actually suspect that the best algorithm doesn't construct a new graph, but works on the original graph, but I can't figure out a good way to do this.) $\endgroup$ – Peter Shor Nov 3 '12 at 12:42
  • $\begingroup$ Can you write something about adding edges in $O(E')$ time ? It's better than brute BFS. We will modified it later. $\endgroup$ – Edger Bachmann Nov 3 '12 at 17:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.