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$ 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$ Nov 3 '12 at 17:23

This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .