Dijkstra's Algorithm Assignment

[tlang07uky]

Hey, I have an assignment due in a few hours, and I can't quite finish it up. I would appreciate if somebody could review the assignment and my code and offer some assistance.

Here is the assignment:

Implement Dijkstra’s shortest-path algorithm. The graph will be given in a text file. We make several assumptions to simplify the implementation. A graph containing n vertexes uses first n capital letters in the alphabet as the names of these vertexes. The file for a graph with n vertexes contains n lines, one for each vertex and the edges starting from that vertex. Each edge is represented by the name of the destination vertex and its length, which is an integer. The names of vertexes and lengths are separated by one or more spaces only. For example, a graph can be represented as:

A B 4 C 2
B D 2 C 3 E 3
C B 1 D 4 E 5
D
E D 1

Where there is a path from A to B of length 4, from A to C of length 2, from B to D of length 2, etc.

Your program will ask the user to input the source node and the destination
node. It will print out the shortest distance between them and the path from the source node to the
destination node. You do not have to implement priority queue for this assignment.

This is what I have so far. I can't figure out how to handle characters, so my program can only read numbers from the text file. It can read three per line, and does so in the following format: [starting node, ending node, length].

Please any prompt help would be awesome!

#include <iostream>
#include <string>
  
using namespace std;

#define GRAPHSIZE 2048 
#define INFINITY GRAPHSIZE*GRAPHSIZE 
#define MAX(a, b) ((a > b) ? (a) : (b)) 
  
int e; //The number of edges in the graph
int n; //The number of nodes in the graph
int dist[GRAPHSIZE][GRAPHSIZE]; 
int d[GRAPHSIZE]; 
  
void output() { 
    int i; 
    for (i = 1; i <= n; ++i) 
        cout << i; //just for reference until i finish
    cout << endl;
    for (i = 1; i <= n; ++i) { 
        cout << d[i]; //just for reference until i finish
    } 
    cout << endl;; 
} 
  
void dijkstra(int x) { 
    int i, k, small; 
    int visited[GRAPHSIZE]; 
  
    for (i = 1; i <= n; ++i) { 
        d[i] = INFINITY; 
        visited[i] = 0; //element i hasn't been visited
    } 
  
    d[x] = 0; 
  
    for (k = 1; k <= n; ++k) { 
        small = -1; 
        for (i = 1; i <= n; ++i) 
            if (!visited[i] && ((small == -1) || (d[i] < d[small]))) 
                small = i; 
  
        visited[small] = 1; 
  
        for (i = 1; i <= n; ++i) 
            if (dist[small][i]) 
                if (d[small] + dist[small][i] < d[i])  
                    d[i] = d[small] + dist[small][i]; 
    } 
} 
  
int main(int argc, char *argv[]) { 
    int i, j; 
    int a, b, c;
  
    FILE *fin = fopen("dist.txt", "r");  //open the file
    fscanf(fin, "%d", &e); 
    for (i = 0; i < e; ++i) 
        for (j = 0; j < e; ++j) 
            dist[i][j] = 0; //set initial dist to zero
    n = -1; 
    for (i = 0; i < e; ++i) { 
        fscanf(fin, "%d%d%d", &a, &b, &c); 
        dist[a][b] = c; 
        n = MAX(a, MAX(b, n)); 
    } 
    fclose(fin); 
  
    dijkstra(1); 
  
    output(); 

    cin >> j;
    return 0; 
}

[tlang07uky]

The name of my text file is "dist.txt"

[fg109]

Is there any reason why you are using C instead of C++ for input? I think it may be helpful to see the actual file you're using as input. I'm not sure of a good way to read in the values if the amount of edges per line is not the same throughout unless I can use getline (which I'm pretty sure is C++).

[tlang07uky]

Sorry, I am working with a friend and he already had some code before I began working, so I just inserted parts of his code into my program and got stuck. I would like for everything to be in C++, but the program compiles as is.

Here are the contents of the text file from which I am required to read:
A B 4 C 2
B D 2 C 3 E 3
C B 1 D 4 E 5
D
E D 1

I framed my code around a text file containing three numbers per line, which is:
10
1 2 10
1 4 5
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4

Where the 10 in the first line represents the number of edges

[fg109]

So that means you've coded your program expecting your input to look like the file you made with only numbers, when the actual input looks completely different...

This is one way to read the input using C++

#include <fstream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    ifstream fin("dist.txt");
    std::string line;
    
    while (getline(fin, line))
    {
        istringstream iss(line);
        char vertex1, vertex2;

        iss >> vertex1;
        while (iss >> vertex2)
        {
            int edgelength; //distance between vertex1 and vertex2
            iss >> edgelength;
            //store the distance and vertices somewhere
        }
    }

    return 0;
}

And here's something using only C that I think may work

#include <cstdio>

int main()
{
    char c;
    FILE *fin = fopen("dist.txt", "r");  //open the file

    c = fgetc(fin);

    while (c != EOF)
    {
        char vertex1, vertex2;
        int edgelength;

        vertex1 = c;
        c = fgetc(fin);

        while (c != '\n' && c != EOF)
        {
            //right now c must be a blank
            vertex2 = fgetc(fin);
            c = fgetc(fin); //another blank
            edgelength = fgetc(fin) - '0';
            c = fgetc(fin);
            //store the vertices and edgelength somewhere
        }

        if (c != EOF)
            c = fgetc(fin);
    }

    fclose(fin);
    return 0;
}

[tlang07uky]

Thank you for your help. I got my program running just in time!

[EEN421]

I have the exact same assignment due tonight! cs315 Tuesday/Thursday with Z. Fei right?

I have an algorithm for running Dijkstra, but it prompts the user for data. I also have a separate function which will read the text file (weird format right?), but I'm having a hard time implementing the read function.

tlang07uky, How did you get yours to run?