Advertisement
Guest User

Untitled

a guest
May 20th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.59 KB | None | 0 0
  1. /*
  2. * To change this license header, choose License Headers in Project Properties.
  3. * To change this template file, choose Tools | Templates
  4. * and open the template in the editor.
  5. */
  6. package javaapplication2;
  7. import java.util.Objects;
  8. import java.util.Random;
  9. import java.util.concurrent.ThreadLocalRandom;
  10.  
  11. /**
  12. *
  13. * @author pc
  14. */
  15. public class JavaApplication2 {
  16.  
  17. /**
  18. * @param args the command line arguments
  19. */
  20. public static Grafas sukurtiGrafaSuNeigiamomisBriaunomis(){
  21. Grafas grafas;
  22. int v = 7;
  23. int b = 12;
  24. grafas = new Grafas(v, b);
  25. // Briauna 1-2
  26. grafas.briaunos[0].pr = 1;
  27. grafas.briaunos[0].pb = 2;
  28. grafas.briaunos[0].svoris = 7;
  29. // Briauna 1-3
  30. grafas.briaunos[1].pr = 1;
  31. grafas.briaunos[1].pb = 3;
  32. grafas.briaunos[1].svoris = 5;
  33. // Briauna 2-3
  34. grafas.briaunos[2].pr = 2;
  35. grafas.briaunos[2].pb = 3;
  36. grafas.briaunos[2].svoris = 3;
  37. // Briauna 2-5
  38. grafas.briaunos[3].pr = 2;
  39. grafas.briaunos[3].pb = 5;
  40. grafas.briaunos[3].svoris = 4;
  41. // Briauna 3-4
  42. grafas.briaunos[4].pr = 3;
  43. grafas.briaunos[4].pb = 4;
  44. grafas.briaunos[4].svoris = 10;
  45. // Briauna 3-5
  46. grafas.briaunos[5].pr = 3;
  47. grafas.briaunos[5].pb = 5;
  48. grafas.briaunos[5].svoris = 3;
  49. // Briauna 4-2
  50. grafas.briaunos[6].pr = 4;
  51. grafas.briaunos[6].pb = 2;
  52. grafas.briaunos[6].svoris = 2;
  53. // Briauna 5-4
  54. grafas.briaunos[7].pr = 5;
  55. grafas.briaunos[7].pb = 4;
  56. grafas.briaunos[7].svoris = 12;
  57. // Briauna 5-6
  58. grafas.briaunos[8].pr = 5;
  59. grafas.briaunos[8].pb = 6;
  60. grafas.briaunos[8].svoris = 4;
  61. // Briauna 5-7
  62. grafas.briaunos[9].pr = 5;
  63. grafas.briaunos[9].pb = 7;
  64. grafas.briaunos[9].svoris = 2;
  65. // Briauna 6-4
  66. grafas.briaunos[10].pr = 6;
  67. grafas.briaunos[10].pb = 4;
  68. grafas.briaunos[10].svoris = 3;
  69. // Briauna 7-6
  70. grafas.briaunos[11].pr = 7;
  71. grafas.briaunos[11].pb = 6;
  72. grafas.briaunos[11].svoris = 3;
  73.  
  74. return grafas;
  75. }
  76.  
  77.  
  78. //--------------------------------------------------------------
  79. public static int[][] trumpiausiKeliai(Grafas grafas, int k){
  80. int v = grafas.v;
  81. int b = grafas.b;
  82. int atstumai[] = new int[v];
  83.  
  84. int ats[][] = new int[2][v];
  85.  
  86. boolean pakeitimas;
  87. // boolean turiNeigiamaCikla = false;
  88.  
  89. for (int i = 0; i < v; i++){
  90. atstumai[i] = Integer.MAX_VALUE;
  91.  
  92. }
  93. atstumai[k-1] = 0;
  94.  
  95. // Briaunu relaksacija
  96. for (int i = 1; i < v; i++) {
  97. pakeitimas = false;
  98. for (int j = 0; j < b; j++) {
  99. int pr = grafas.briaunos[j].pr-1;
  100. int pb = grafas.briaunos[j].pb-1;
  101. int svoris = grafas.briaunos[j].svoris;
  102. if (atstumai[pr] != Integer.MAX_VALUE && atstumai[pr] + svoris < atstumai[pb]) {
  103. atstumai[pb] = atstumai[pr] + svoris;
  104. pakeitimas = true;
  105. }
  106. }
  107. if (!pakeitimas)
  108. break;
  109. }
  110.  
  111. ats[0] = atstumai;
  112. //ats[1] = prec;
  113. return ats;
  114.  
  115. }
  116. public static void spausdinti(int atstumai[], int v, int k){
  117. for (int i = 0; i < v; i++) {
  118. //int einamasis = prec[i];
  119. // if (atstumai[i] != Integer.MAX_VALUE) {
  120. System.out.print("Atstumas nuo virsunes " + k + " iki " + (i+1) + " = " + atstumai[i] + ";\t");
  121. /*
  122. if ((i+1) != k) {
  123. System.out.print("Kelias: " + (i + 1) + "->");
  124. while (einamasis != k) {
  125. System.out.print(einamasis + "->");
  126. einamasis = prec[einamasis - 1];
  127. }
  128. System.out.print(k);
  129. }
  130. */
  131.  
  132. System.out.println();
  133. // }
  134. // else
  135. // System.out.println("Atstumas nuo virsunes " + (i + 1) + " iki " + k + ": NEIMANOMA PRIEITI");
  136. }
  137. }
  138.  
  139. public static void main(String[] args) {
  140.  
  141. int ats[][];
  142. Grafas grafas = sukurtiGrafaSuNeigiamomisBriaunomis();
  143. ats = trumpiausiKeliai(grafas, 1);
  144. // if (ats != null)
  145. spausdinti(ats[0], 7, 1);
  146. // else
  147. // System.out.println("Grafas turi neigiama cikla, trumpiausiu keliu tiksliai apskaiciuoti negalima.");
  148. }
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement