Thread: Longest Distance - Graph Theory

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Longest Distance - Graph Theory

    Suppose I have a adjacency matrix of a simple graph. Can anyone provide me some idea/algorithm to find the longest distance between any 2 vertices? I need it to find eccentricity of each vertex of a graph.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You don't want to find the longest distance between any two vertices, which doesn't exist anyway (imagine a triangular cycle; I can get from A to C in as many steps as I want, by just going back and forth from A to B until I get tired, and then going to C).

    What you want to find is the first n such that every other node is reachable in at most n steps. The standard interpretation of (A)^n will come in handy here.

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Sorry, did not get properly! Can you be please more elaborate!!

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    He's saying that your formulation of the problem is misleading.

    What you're looking for is the longest minimal path of the graph. I believe using an all_pairs_shortest_path algorithm followed by selecting the maximum of the results should yield a solution. I don't know if that's the most efficient way of doing it.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Oh I see!!! Are you sure that it would work? I am not saying about your knowledge. I am saying it because I have it implement in the project!! So making it sure!

  6. #6
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    What you can do is run a bfs to completion and choose the last instance of visit to your destination node. Alternatively, if you have weighed edges, you can use Dijkstra's algorithm. You might want to first run a cycle finding algorithm to find cycles in your graph. In case of cycles on the intended path, you would have a path of infinite length from your start node to the end node.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graph Theory Problems
    By anirban in forum Tech Board
    Replies: 1
    Last Post: 06-26-2007, 12:14 PM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  3. shortest path problems
    By talz13 in forum C++ Programming
    Replies: 7
    Last Post: 05-08-2004, 06:13 AM
  4. Graph Theory
    By xds4lx in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 12-17-2002, 12:58 PM
  5. FYI: Graph theory book for download
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-20-2002, 10:03 AM