Bellman Ford algorithm - unknown weight

This is a discussion on Bellman Ford algorithm - unknown weight within the Tech Board forums, part of the Community Boards category; Hi to everyone!!! I have the following problem: I have a directed graph and I want to find out whether ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    25

    Bellman Ford algorithm - unknown weight

    Hi to everyone!!! I have the following problem:
    I have a directed graph and I want to find out whether there are any negative cycles using Bellman Ford algorithm. I know the weight of all of the edges in this graph but one (the weights of the edges derive from an exercise).
    1) Can I use Bellman Ford with one edge's unknown weight?
    2) If not, how can I later calculate its weight using Bellman Ford?

    I don't want a code but I need help with understanding its application.

  2. #2
    Registered User
    Join Date
    Dec 2011
    Posts
    25
    Noone can help me?

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    You can't "calculate" an unknown weight without some other constraint (like all cycles have the same total weight).

    Code:
     A   10    B
      +--->---+
      |       |
    X V       V 30
      |       |
      +--->---+
     C   20    D
    Without additional information, X could be any value at all. Imagine these were cities on a map, and the weights were road distances. All that you know about C is that it is on a circle 20 miles radius from D, but it tells you nothing about how far that is away from A.

    If ABD and ACD are the same overall, you can work out X.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    25
    I see. Quite impressive that you chose distance of cities as an example as it is right this thing that I am working on.
    I have a graph exactly as shown in this pdf (page 3): http://www.st.ewi.tudelft.nl/~planke.../mscthesis.pdf

    I don't have information about the edge x0x3. Would it be arbitrary to work around it? And what about the fact that it is asked to calculate the weight of the edge x0x3?

  5. #5
    Registered User
    Join Date
    Dec 2011
    Posts
    25
    And before you mention that there is no edge x0x3, I should say that the description of the problem doesn't point it out technically as an edge (hence the picture of the graph) but it does exist realistically (regarding also the fact that it is later asked to be calculated).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. head gasket replacement 94 ford ranger
    By Annonymous in forum General Discussions
    Replies: 13
    Last Post: 05-02-2012, 10:37 PM
  2. Weight/height Problem
    By SMAlvarez in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2007, 05:40 PM
  3. Your Weight On Planets
    By Trekkie in forum C++ Programming
    Replies: 16
    Last Post: 10-23-2005, 11:01 PM
  4. losing weight
    By Shadow in forum A Brief History of Cprogramming.com
    Replies: 20
    Last Post: 10-21-2002, 05:43 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21