How to Represent a Graph using Dijkstra's Algorithm, Given a .txt file as Input

Question

I'm having trouble using Dijkstra's algorithm when given a text file in this format.

The first line represents the number of vertexes. Should I store this value as a 2-Dimensional Array?

I was thinking that I could have the second part of the 2D array be the actual value each vertex holds.

For example vertex 3 holds 78. Vertex 4 holds 87... etc.

The problem I run into is having to store the edges. 1 4 98 Where 1 is vertex 1, 4 is vertex 4, and the distance between them is 98. How would I store this value of 98?

I'm just stumped here, any advice would be greatly appreciated.

Below is the input

Number of Vertexes Number of Edges Vertex NumValue Vertex Vertex NumValue

Where if there are two vertexes, the NumValue that comes after is the Distance between the two.

Input

5 7 3 78 4 87 5 98 1 4 98 5 4 45 1 5 140 4 3 87 2 5 150 3 5 109 3 2 73

Output

388

Consider changing the title of this question to something like "how to represent a graph for dijkstra's algorithm" or better "how to represent a weighted graph" as that is more closely related to what you're trying to do. And ... it also might suggest some searches you could do that would get you an answer. — davidbak
– davidbak, Commented May 6, 2016 at 16:59

smac89 · Accepted Answer · 2016-05-06 17:03:53Z

0

There are many ways to do this, here are some:

public class Edge {
    private class Node {
        private int value;
    }

    private Node from, to;
    private double distance;
}

With this, you can have an arraylist of Edges to represent the graph

public class Graph {
    private class Node {
        private Node adjacent;
        private double distance;
        private int value;
    }

    private Node[] nodes;
}

Here you create a graph class which contains a list of nodes

public class Graph {
    private double[][] matrix;
}

Again this is a graph class but using a matrix. If node 1 has an edge to node 5 with distance 75.9, then matrix[1][5] == 75.9

answered May 6, 2016 at 17:03

smac89

43.8k15 gold badges150 silver badges204 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

SweetJD14 Over a year ago

I want to go with creating a graph class which contains a list of nodes, would you mind further explaining how I can read in the text file on the command line, to store these values in the matrix like so?

smac89 Over a year ago

@SweetJD14 You might want to either ask a new question, or look at this answer

Denis Savin · Accepted Answer · 2016-05-06 17:06:10Z

0

check this approach to represent edge weighted graph http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/EdgeWeightedGraph.java.html

answered May 6, 2016 at 17:06

Denis Savin

1

1 Comment

Denis Savin Over a year ago

They also represent an edge using this class algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/…

Collectives™ on Stack Overflow

How to Represent a Graph using Dijkstra's Algorithm, Given a .txt file as Input

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related