# Graphs, Dijkstra's algorithm

Printable View

• November 11th 2011, 03:47 AM
token22
Graphs, Dijkstra's algorithm
Hello,

I've got some problems to solve and would appreciate any advice.

a) Give an example of graph which involves negative edge path costs and nevertheless Dijkstra's algorithm finds shortest path from any vertex (but not from all of them).

b) Give an example of graph which involves negative edge path costs and nevertheless Dijkstra's algorithm finds shortest path from all vertices.

c) Give an example of graph and its vertex such that output of Dijstra's algorithm woun't be shortest paths from given vertex (compare shortest paths from algorithm with real shortest path from given vertex).

d) Determine all $n \in N$ for which the following applies: removing any two edges of the graph $K_n$ there is no more than (n - 3)-connected graph.

Thanks
Token
• November 11th 2011, 08:48 AM
token22
Re: Graphs, Dijkstra's algorithm
a)
http://i39.tinypic.com/20giqs0.png
b)
http://i44.tinypic.com/eu0opl.png
c)
http://i42.tinypic.com/icolq9.png
Starts from A
d) $n=3$ When we remove 2 edges from complete graph $K_3$ we will get disconnected graph which is 0-connected. (correct me if i am wrong please).

What do you think?
• November 11th 2011, 03:20 PM
token22
Re: Graphs, Dijkstra's algorithm
Well, i hope my results are correct as anybody didn't reply.
Now I got another Problem to solve:

Consider the following algorithm for finding shortest paths in undirected final graph that can involve negatively weighted edges. Let's say the smallest value of edge will be $h$. Then we add $\left | h \right |$ to all edges. Now all of our edges are positively weighted. Choose vertex (let's say $v$) and run Dijkstra's algorithm on this vertex. Prove or disprove that with this way we get the shortest paths from vertex $v$ in previous given graph (from length of shortest path to arbitary vertex found by Dijkstra's algorithm we should subtract $k.\left | h \right |$, where $k$ is length of path).

Firstly I thought that this doesn't work, but I found THIS , where somebody wrote that is should work. And also found something like Johnson's algorithm that seems to be similar. So i am now little confused. If you could help me with this at least.
thanks
token