Results 1 to 4 of 4

Thread: The shortest path in a directed graph, Dijkstra algorithm

  1. #1
    Join Date
    Feb 2008
    Posts
    324

    The shortest path in a directed graph, Dijkstra algorithm

    I'm looking for a java algorithm to find the shortest path in a directed graph from the vertex 1 to vertex n and through k vertices. This last condition that I have a problem. I thought of course use the Dijkstra algorithm. What do you think? And how to modify it to pass through k vertices?

  2. #2
    Join Date
    May 2008
    Posts
    271

    Re: The shortest path in a directed graph, Dijkstra algorithm

    When you say "going through k vertices," you mean that you are looking for a path from a vertex of v and going to another vertex of x and size at least k, or from v to x and passing through at least each vertex of a K?

  3. #3
    Join Date
    Feb 2008
    Posts
    324

    Re: The shortest path in a directed graph, Dijkstra algorithm

    I want to find the path from the vertex s to vertex t and through k distinct vertices. That is, it must impose an exact number of k vertices.

  4. #4
    Join Date
    May 2008
    Posts
    271

    Re: The shortest path in a directed graph, Dijkstra algorithm

    In this case, make a journey of your graph in Dijkstra and instead store the shortest path for each vertex, remember all the paths leading to the vertex with their length in terms of distinct nodes.

Similar Threads

  1. Adobe reader close by DEP when directed to print
    By Yogisa in forum Windows Software
    Replies: 4
    Last Post: 16-09-2011, 12:09 AM
  2. SandyBridge mainboard support Intel VT-d Technology Directed I/O
    By Lyudmyla in forum Motherboard Processor & RAM
    Replies: 6
    Last Post: 16-07-2011, 10:18 AM
  3. Replies: 6
    Last Post: 04-06-2010, 12:15 AM
  4. Replies: 0
    Last Post: 23-03-2009, 11:32 PM
  5. Replies: 3
    Last Post: 11-11-2008, 06:19 PM

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Page generated in 1,714,103,040.23083 seconds with 16 queries