Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.99 KB | None | 0 0
  1. ArrayList<Vertex> vertices;
  2. ArrayList<Edge> edges;
  3.  
  4. void setup() {
  5. size(1000, 1000);
  6. vertices = new ArrayList<Vertex>();
  7. edges = new ArrayList<Edge>();
  8. randomSeed(22);
  9. fillVertices();
  10. fillEdges();
  11. }
  12.  
  13. void draw() {
  14. background(0);
  15. stroke(255);
  16.  
  17. for (Vertex v : vertices) {
  18. if (vertices.indexOf(v) == 7) {
  19. fill(255, 0, 0);
  20. }
  21. circle((v.x + 1) * 19, (v.y + 1) * 19, 10);
  22. fill(255);
  23. }
  24.  
  25. for (Edge e : edges) {
  26. line((e.v1.x + 1) * 19, (e.v1.y + 1) * 19, (e.v2.x + 1) * 19, (e.v2.y + 1) * 19);
  27. }
  28.  
  29. calculateSPT(vertices.get(0));
  30. println(getShortestPathTo(vertices.get(7)));
  31. }
  32.  
  33. class Vertex implements Comparable<Vertex> {
  34. int x, y, id, csf;
  35. double minDistance;
  36. Vertex previous;
  37.  
  38. Vertex (int num, int xpos, int ypos) {
  39. minDistance = 999999999999999999999999999999.;
  40. id = num;
  41. x = xpos;
  42. y = ypos;
  43. csf = 0;
  44. }
  45.  
  46. ArrayList<Edge> adjacencies() {
  47. ArrayList<Edge> adjacencies = new ArrayList<Edge>();
  48.  
  49. for (Edge e : edges) {
  50. if (e.v1.equals(this)) {
  51. adjacencies.add(e);
  52. }
  53. }
  54.  
  55. return adjacencies;
  56. }
  57.  
  58. @Override
  59. public int compareTo(Vertex other) {
  60. if (this.csf > other.csf) {
  61. return 1;
  62. } else if (this.csf == other.csf) {
  63. return 0;
  64. } else {
  65. return -1;
  66. }
  67. }
  68. }
  69.  
  70. class Edge {
  71. Vertex v1;
  72. Vertex v2;
  73. int weight;
  74.  
  75. Edge(Vertex v, Vertex v0, int w) {
  76. v1 = v;
  77. v2 = v0;
  78. weight = w;
  79. }
  80. }
  81.  
  82. void fillEdges() {
  83. // for each vertex pick a random number 2-5 and generate an edge
  84. // to a random vertex with a weight based on its distance in space
  85. // times a random factor
  86.  
  87. for (Vertex v : vertices) {
  88. int numEdges = 1; //round(random(2, 5));
  89. //for (int i = 0; i < numEdges; i++) {
  90. Vertex vertex = vertices.get(round(random(0, 9)));
  91. if (vertex.equals(v)) {
  92. vertex = vertices.get(round(random(0, 9)));
  93. }
  94. int weight = int(dist(v.x, v.y, vertex.x, vertex.y) * random(0, 2));
  95.  
  96. edges.add(new Edge(v, vertex, weight));
  97. //}
  98. }
  99. }
  100.  
  101. void fillVertices() {
  102. for (int i = 0; i < 10; i++) {
  103. int x = round(random(0, 50));
  104. int y = round(random(0, 50));
  105.  
  106. vertices.add(new Vertex(i, x, y));
  107. }
  108. }
  109.  
  110. import java.util.Collections;
  111. import java.util.PriorityQueue<E>;
  112.  
  113. void calculateSPT(Vertex start) {
  114. start.minDistance = 0.;
  115. PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
  116. vertexQueue.add(start);
  117.  
  118. while (!vertexQueue.isEmpty()) {
  119. Vertex u = vertexQueue.poll();
  120.  
  121. for (Edge e : u.adjacencies()) {
  122. Vertex v = e.v2;
  123. int weight = e.weight;
  124. double costSoFar = u.minDistance + weight;
  125. if (costSoFar < v.minDistance) {
  126. vertexQueue.remove(v);
  127.  
  128. v.minDistance = costSoFar;
  129. v.previous = u;
  130. vertexQueue.add(v);
  131. }
  132. }
  133. }
  134. }
  135.  
  136. ArrayList<Vertex> getShortestPathTo(Vertex target) {
  137. ArrayList<Vertex> path = new ArrayList<Vertex>();
  138. for (Vertex v = target; v != null; v = v.previous) {
  139. path.add(v);
  140. }
  141.  
  142. Collections.reverse(path);
  143. return path;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement