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 for which the following applies: removing any two edges of the graph there is no more than (n - 3)-connected graph.

Thanks

Token

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) When we remove 2 edges from complete graph we will get disconnected graph which is 0-connected. (correct me if i am wrong please).

What do you think?

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 . Then we add to all edges. Now all of our edges are positively weighted. Choose vertex (let's say ) and run Dijkstra's algorithm on this vertex. Prove or disprove that with this way we get the shortest paths from vertex in previous given graph (from length of shortest path to arbitary vertex found by Dijkstra's algorithm we should subtract , where 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