0

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

SweetJD14
  • 73
  • 1
  • 2
  • 11
  • 1
    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 May 06 '16 at 16:59

2 Answers2

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

smac89
  • 39,374
  • 15
  • 132
  • 179
  • 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? – SweetJD14 May 06 '16 at 17:12
  • @SweetJD14 You might want to either ask a new question, or look at [this answer](http://stackoverflow.com/a/304061/2089675) – smac89 May 06 '16 at 17:18
0

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

Denis Savin
  • 1
  • They also represent an edge using this class http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Edge.java.html – Denis Savin May 06 '16 at 17:08