Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite

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

Output:

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

share|improve this question
I don't understand the output of your second example at all. Is there a typo? – Peter Shor Nov 2 '12 at 18:46
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. – Edger Bachmann Nov 2 '12 at 19:13
I see ... I missed the "no direct path" in the problem statement. – Peter Shor Nov 2 '12 at 19:15
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.) – Peter Shor Nov 3 '12 at 12:42
Can you write something about adding edges in $O(E')$ time ? It's better than brute BFS. We will modified it later. – Edger Bachmann Nov 3 '12 at 17:23
show 7 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.