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

Thanks

Token