Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Dijkstra's algorithm

Name: Anonymous 2013-10-26 23:05

Hi /prog/. I'm having some issues with the way I implemented dijkstra's algorithm. Can you guys see if you can spot any errors or anything weird? I tried to comment as best as I can.
Here is the .cpp file

// ---------------------------------------------------------------------------
// findShortestPath
// Finds the shortest path between each node using Dijkstra's algorithm. Implemented
// using private arrays: T for the shortest distance between nodes, pathing, and
// marking for being visited; and C to record the nodes and the distances between
// them.
void GraphM::findShortestPath()
{
    int V;

    for(int source = 1; source <= size; source++) //loop for each node
    {
        T[source][source].dist = 0;
        T[source][source].visited = true;
        T[source][source].path = source;
        V = source;

        for(int numRuns = 1; numRuns < size ; numRuns++) //Main loop for for 'V'
        {
            for(int W = 1; W <= size; W++) //Loop for the 'W' component
            {
                if(C[V][W] == INFINITY || T[source][W].visited == true)
                    continue; //Skips this 'W' if the node is visited or distance is infinite
                else if(T[source][W].dist > T[source][V].dist + C[V][W]) //Sets shortest distance
                {
                    T[source][W].dist = T[source][V].dist + C[V][W];
                    T[source][W].path = V;
                }
            }

            T[source][V].visited = true;
            V = findShortestPathHelper(source);
        }
        T[source][V].visited = true; //Set last node to visited

    }
    //cout << "Distance from 1 to 2: " << T[1][2].dist << endl;
}

// findShortestPathHelper
// **Helper Method for findShortestPath**
// Finds the unvisited node with the lowest distance for the V component of
// Dijkstra's algorithm.
int GraphM::findShortestPathHelper(int source)
{
    int min = 0;

    for(int i = 1; i <= size; i++)
    {
        if(T[source][i].dist < T[source][min].dist && T[source][i].visited == false)
            min = i;
    }

    return min;
}

Name: Anonymous 2013-10-26 23:08

and the header file. I didn't post the other functions because they would take up this entire section.


#include "NodeData.h"
#include <iostream>
#include <fstream>
using namespace std;

class GraphM {
public:
    static const int MAXNODES = 50;
    static const int INFINITY = 9999;
    GraphM() ;

    void buildGraph(ifstream&);
    void findShortestPath();
    void displayAll();
    void display(int, int);

private:
    struct TableType {
        bool visited; // whether node has been visited
        int dist; // shortest distance from source known so far
        int path; // previous node in path of min dist
    };
    NodeData data[MAXNODES]; // data for graph nodes information
    int C[MAXNODES][MAXNODES]; // Cost array, the adjacency matrix
    int size; // number of nodes in the graph
    TableType T[MAXNODES][MAXNODES]; // stores visited, distance, path

    int findShortestPathHelper(int);    // helper method for findShortestPath
    bool checkInput(int, int);            // assures graph input from file is valid
    void displayAllHelper(int, int);    // helper method for display all
    void displayPath(int, int, int);    //displays from source to a node in a level
    void displayHelper(int, int, int);    // helper method for display
};

Name: Anonymous 2013-10-26 23:12

Basically, I first have to find V using the first couple loops, and then marking V, then going through all the adjacent nodes from V and finding out which nodes cost less to go through, then update distances and rinse and repeat until no more Vs can be found.

Any help/criticism/insult would greatly appreciated

Name: Anonymous 2013-10-27 0:05

That's some real Enterprise Quality shit right there. You should submit your résumé to Oracle as quickly as possible.

Name: Anonymous 2013-10-27 0:45

honor code, bitch

Name: Anonymous 2013-10-27 1:45

>─────▄████▀█▄
>───▄█████████████████▄
>─▄█████.▼.▼.▼.▼.▼.▼▼▼▼
>▄███████▄.▲.▲▲▲▲▲▲▲▲
>███████████████████▀▀
YOU HAVE BEEN CAUGHT BY THE NIGGER OF DOOM! REPOST THIS 5 TIMES OR GET NIGGERED!!!

Name: Anonymous 2013-11-03 6:54

*YOU HAVE BEEN VISITED BY LE TOP LEL OF COMEDY GOLD** POST THIS IN 3 threads or lose your sides!
░░░░░░░▄▀▀▀░▄▄▄▄░░░▀▀▀▀▀▀▀▀▄▄░▀
░░░░░░░█░░░░░░░░▀▀▀▀▀▄▄▄▄▄▄▄▄▀░░█
░░░░░▄▀░░░░░░░░░░▄░░░░░░░░▄▄░░░░░▀▄
░░░▄▀░░░░░▄▀▀▀█▄░▀░░░░▄▀▀▀██▀▀▄░░░░░▀
░░▄▀░░▄▄░░▀▀▀▀████▀░░░▀▄▄▀▀▀▀▄█░░░░░░█
░▄▀░▄▀█░░▄▄░░░░░░░█░░░░░▄▄▄░░░▀▀░░░░░░█
▄▀░░█░█░▀░░▀▀▄░░░░░█░░░░░░░▀▀▀▀▀▄░░░░░█
▀▄░░▀░█░░░▄░░░░░░▄▀░░░░▀▄░░░▄▄░░▀▄░█░▄▀
░░▀▄░░░░█▀▄░░░░░▀█░░░░▀▀░█▄▀▄░█░░░█░█
░░░░█░░█░▀▄▀▄▄░░░░▀▀▀░░░▄█▀░▄▀█░░░░▄
░░░░░█░░█░▀▀▄░▀▄▄▄▄▄▄▄▀█░▄█▀▄▀░░░░░
░░░░░█░░▀▄▄░░▀█░░░█░░▄▄▀▀▄▄█▀░░░░▀
░░░░▄▀░░░▀▄▀▀▄░▀▀▀▀▀▀▄▄▀▀▀▄▀░░░░▀
░░░▄▀░░░░░░▀▄░█▄▄▄▄▀▀░▀▄▀▀░░░▄▀▀
░░▄▀░░░░░░░░░▀▄▄▄▄█▄▄▀▀░░░░▄
░░█░░░░░░▀▄▄░░░▄▄▄▄▄▄▀░░░▄▀
░░█░░░░░░░░░▀▀▀▄▄▄▄▄▄▄▀▀
░░░█░░░░░░▀▀▀▀▀░░░░▄
░░░▀▀▄▄▄▄▄▄▄▄▄▀▀▀

Name: Anonymous 2013-11-03 13:20

That's not Dijkstra's algorithm, faggot. Dijkstra's algorithm is "complain about every language that isn't Lisp or Algol."

Name: Anonymous 2013-11-03 15:31

Diks

Don't change these.
Name: Email:
Entire Thread Thread List