Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ArrayList<Vertex> vertices;
- ArrayList<Edge> edges;
- void setup() {
- size(1000, 1000);
- vertices = new ArrayList<Vertex>();
- edges = new ArrayList<Edge>();
- randomSeed(22);
- fillVertices();
- fillEdges();
- }
- void draw() {
- background(0);
- stroke(255);
- for (Vertex v : vertices) {
- if (vertices.indexOf(v) == 7) {
- fill(255, 0, 0);
- }
- circle((v.x + 1) * 19, (v.y + 1) * 19, 10);
- fill(255);
- }
- for (Edge e : edges) {
- line((e.v1.x + 1) * 19, (e.v1.y + 1) * 19, (e.v2.x + 1) * 19, (e.v2.y + 1) * 19);
- }
- calculateSPT(vertices.get(0));
- println(getShortestPathTo(vertices.get(7)));
- }
- class Vertex implements Comparable<Vertex> {
- int x, y, id, csf;
- double minDistance;
- Vertex previous;
- Vertex (int num, int xpos, int ypos) {
- minDistance = 999999999999999999999999999999.;
- id = num;
- x = xpos;
- y = ypos;
- csf = 0;
- }
- ArrayList<Edge> adjacencies() {
- ArrayList<Edge> adjacencies = new ArrayList<Edge>();
- for (Edge e : edges) {
- if (e.v1.equals(this)) {
- adjacencies.add(e);
- }
- }
- return adjacencies;
- }
- @Override
- public int compareTo(Vertex other) {
- if (this.csf > other.csf) {
- return 1;
- } else if (this.csf == other.csf) {
- return 0;
- } else {
- return -1;
- }
- }
- }
- class Edge {
- Vertex v1;
- Vertex v2;
- int weight;
- Edge(Vertex v, Vertex v0, int w) {
- v1 = v;
- v2 = v0;
- weight = w;
- }
- }
- void fillEdges() {
- // for each vertex pick a random number 2-5 and generate an edge
- // to a random vertex with a weight based on its distance in space
- // times a random factor
- for (Vertex v : vertices) {
- int numEdges = 1; //round(random(2, 5));
- //for (int i = 0; i < numEdges; i++) {
- Vertex vertex = vertices.get(round(random(0, 9)));
- if (vertex.equals(v)) {
- vertex = vertices.get(round(random(0, 9)));
- }
- int weight = int(dist(v.x, v.y, vertex.x, vertex.y) * random(0, 2));
- edges.add(new Edge(v, vertex, weight));
- //}
- }
- }
- void fillVertices() {
- for (int i = 0; i < 10; i++) {
- int x = round(random(0, 50));
- int y = round(random(0, 50));
- vertices.add(new Vertex(i, x, y));
- }
- }
- import java.util.Collections;
- import java.util.PriorityQueue<E>;
- void calculateSPT(Vertex start) {
- start.minDistance = 0.;
- PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
- vertexQueue.add(start);
- while (!vertexQueue.isEmpty()) {
- Vertex u = vertexQueue.poll();
- for (Edge e : u.adjacencies()) {
- Vertex v = e.v2;
- int weight = e.weight;
- double costSoFar = u.minDistance + weight;
- if (costSoFar < v.minDistance) {
- vertexQueue.remove(v);
- v.minDistance = costSoFar;
- v.previous = u;
- vertexQueue.add(v);
- }
- }
- }
- }
- ArrayList<Vertex> getShortestPathTo(Vertex target) {
- ArrayList<Vertex> path = new ArrayList<Vertex>();
- for (Vertex v = target; v != null; v = v.previous) {
- path.add(v);
- }
- Collections.reverse(path);
- return path;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement