Results 1 to 12 of 12
  1. #1
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default help ... i have a problem withe dijkstra algorthim

    :)hi all;

    I have the code of the static dijkestra algorithm and i want to converted to be dynamic, but i really got stuck . i have the layout code but i didn't understand it. So any one who has experiance in the Dijkstra algorithm can help me.

    this is the static dijkstra algorithm java source:

    package DijkstraAlgorithm.src.graphs;

    import java.util.Hashtable;

    /**
    * @author vsutskever
    *
    */
    public class Dijkstra {


    private Graph graph;
    //priority queue stores all of the nodes, reachable from the start node
    //The queue is sorted by the node.distance
    private GraphNodePriorityQueue priorityQ = new GraphNodePriorityQueue();
    private Hashtable <GraphNode,Integer> distance = new Hashtable<GraphNode, Integer>();

    //1. needs to get the list of all nodes in the graph
    //2. need to initialize distance vector to infinity
    //3. Need Edge Cost function
    public Dijkstra (Graph g){
    this.graph = g;
    this.graph.getStartNode().setDistance(0);
    this.priorityQ.add(this.graph.getAllNodes());
    }
    /**
    * Actual algorithm
    */
    public void go(){
    while (this.priorityQ.hasMore()){
    GraphNode n = this.priorityQ.remove();
    for (Edge e: n.getOutGoingEdges()){
    GraphNode adjNode = e.getNode();
    Integer newPossiblePathCost = e.getCost()+n.getDistance();
    if (newPossiblePathCost<adjNode.getDistance()){
    adjNode.setDistance(newPossiblePathCost);
    this.priorityQ.updateGraphNodeDistance(adjNode);
    }
    }
    }
    }
    /**
    *
    */
    public void PrintStatusOfPriorityQ(){
    this.priorityQ.PrintContents();
    }



    }

    and this is the layout code for the dynamic:

    Dijkstra_Double_Bucket:
    INPUTS:
    V, the set of nodes in the network
    E, the set of arcs in the network
    C, max(||e||), "eE
    s, the source node, sV
    B, a constant used to determine number of buckets
    e.g. largest power of 2 <C
    OUTPUTS:
    P, the set of parent nodes on shortest paths to nearest
    source
    VARIABLES:
    High, an array of Lists
    Low, an array of Lists
    let source sV have d(s)0, S(s)labelled
    let all other nodes vV have d(s), S(s)unreached
    Num(C+1)/B
    Low: array [0..B] of List
    High: array [0..Num] of List
    Insert(Low[0],s)
    for L in 0 to Num loop
    for P in 0 to B loop
    while Empty(Low[P]) loop
    Scan(Head(Low[P]))
    for all {w|(Head(Low[P]),w) E S(w)=labelled} loop
    if d(w)>((L+1)B - 1) then
    /* INSERT IN UPPER BINS */
    Insert(High[d(w)/B],w)
    else
    /* INSERT IN LOWER BINS */
    Insert(Low[d(w) - LB], w)
    end if
    end loop
    Remove(Low[L], Head(Low[L]))
    end loop
    end loop
    end loop

    So can any one help me please.....:p

  2. #2
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default i am sad

    17 views .... and no one help me:confused:...

  3. #3
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default

    38 views .... and no one help me...

    i really need the help.. no one of you have an experiance in dijkstra.....

  4. #4
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    1. Can't really read the code. There are lots of strange characters and you should use CODE tags.
    2. What have you tried? What is the specific problem? We're not here to do coding work for free.

  5. #5
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default

    i didn't ask you for coding...

    I face a problem with my code and i want a proffisional one in Dijkstra to solve it....

  6. #6
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    I would be happy to help but the code you have provided is very difficult to read. It looks like you have tried to copy and paste text with non-ASCII characters in it and it hasn't worked properly.
    What is the source of the "layout code" that you have and what exactly do you want to achieve by making the code "dynamic"?

  7. #7
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default

    hello OrangeDog...

    I want to change the static to dynamic for my project..
    it seems that iwas wrong since this layout fro static not dynamic...

    thanks for trying to help , i really appreciate it...

    i will try to search for another layout to help me to write the right code for dynamic...

    thanks a gain^^

  8. #8
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    What do you mean by dynamic? Is it just a different implementation of a priority queue? For the largest connected data sets, a Fibonacci Heap is the best current data structure.

  9. #9
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default

    yes you are right i was mistaken...

    i face this problem now when i tried to run the project...

    log4j:WARN No appenders could be found for logger (graphs).
    log4j:WARN Please initialize the log4j system properly.

    it seems that there is a problem with the log4j file...

    do you know how to solve it??

  10. #10
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    Don't know what a log4j file is. Presumably you're using some kind of library you haven't told us about. I would suggest looking at its documentation.

  11. #11
    shamsa is offline Member
    Join Date
    Mar 2009
    Posts
    13
    Rep Power
    0

    Default

    it is a very huge documentation ... so i can't posted....

    Log4j is an open source tool developed for putting log statements into your application. It was developed by the good people at Apache's Jakarta Project. It's speed and flexibility allows log statements to remain in shipped code while giving the user the ability to enable logging at runtime without modifying any of the application binary. All of this while not incurring a high performance cost.

    ^^

  12. #12
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    I didn't mean post it here, I mean read it in order to work out what the problem is. If you're still stuck after that then try asking a more specific question, including any code that is throwing exceptions.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •