Results 1 to 3 of 3

Math Help - Graphs, Dijkstra's algorithm

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    23

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2011
    Posts
    23

    Re: Graphs, Dijkstra's algorithm

    a)

    b)

    c)

    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?
    Last edited by token22; November 11th 2011 at 12:24 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    23

    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
    Last edited by token22; November 12th 2011 at 04:33 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Yen's algorithm - shortest path - Graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 12th 2009, 11:52 AM
  2. Replies: 4
    Last Post: May 10th 2009, 09:29 AM
  3. Graphs (algorithm)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 8th 2008, 03:06 PM
  4. dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 6th 2008, 11:16 AM
  5. LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2007, 06:45 PM

/mathhelpforum @mathhelpforum