graph Java:Dijkstra算法使用随机边更改边数
我有一个程序可以实现Dijkstra的图形算法。我要创建一个有10个顶点和30条随机边的图。但是，我不知道如何精确获得30条边。我有代码，但我似乎找不到需要更改的地方，因此每次运行代码时我都会得到30条边。我知道这很简单，但我不得不将代码从读取带有边缘的文件更改为随机分配它们。现在我有16个优势。任何帮助创建我的图形，正好有30条边将是伟大的
代码如下：
图形类：
package TestGraphs;
import TestGraphs.Vertex;
import java.util.ArrayList;
import java.util.Iterator;
public class Graph {
public Vertex[] vertex;
public double[] centerVert;
public double[][] weight; // weight[i][j] >= 0.0 indicates an edge
public double center;
public int centerV;
public Graph(int numVertices) {
vertex = new Vertex[numVertices];
weight = new double[numVertices][numVertices];
centerVert = new double[numVertices];
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
weight[i][j] = -1.0; // no edge
}
}
}
public void createAdjacencyLists() {
for (int i = 0; i < vertex.length; i++) {
vertex[i].neighbors = new ArrayList<Vertex>();
for (int j = 0; j < vertex.length; j++) {
if (j != i && weight[i][j] > 0.0) {
vertex[i].neighbors.add(vertex[j]);
}
}
}
}
public void printGraph() {
System.out.println("Vertices:");
for (int i = 0; i < vertex.length; i++) {
System.out.println(i + ": " + vertex[i]);
}
System.out.println("Edges:");
for (int i = 0; i < vertex.length; i++) {
System.out.print(vertex[i] + " neighbors:");
for (int j = 0; j < vertex.length; j++) {
if (j != i && weight[i][j] > 0.0) {
System.out.print(" " + vertex[j] + "w:" + String.format("%.2f", weight[i][j]));
centerVert[i] = weight[i][j] + centerVert[j];
}
}
System.out.println();
}
for (int k = 1; k < vertex.length; k++) {
center = centerVert[0];
if (center > centerVert[k]) {
centerV = k;
}
}
System.out.println("The center vertex is " + vertex[centerV]);
}
ArrayList<Vertex> breadthFirstSearch(Vertex source) {
ArrayList<Vertex> queue = new ArrayList<Vertex>();
ArrayList<Vertex> visited = new ArrayList<Vertex>();
// mark all vertices as not visited:
for (int i = 0; i < vertex.length; i++) {
vertex[i].visited = false;
}
source.visited = true;
queue.add(source);
while (!queue.isEmpty()) {
Vertex head = queue.remove(0);
visited.add(head);
for (Iterator<Vertex> iter = head.neighbors.iterator(); iter.hasNext();) {
Vertex neighbor = iter.next();
if (!neighbor.visited) {
neighbor.visited = true;
queue.add(neighbor);
}
}
}
return visited;
}
// Dijkstra's algorithm:
public void dijkstra(Vertex source) {
ArrayList<Vertex> VminusS = new ArrayList<Vertex>();
for (int i = 0; i < vertex.length; i++) {
vertex[i].d = Double.MAX_VALUE; // + infinity
vertex[i].pred = null;
VminusS.add(vertex[i]);
}
source.d = 0.0;
while (!VminusS.isEmpty()) {
Vertex smallestDVertex = null;
for (Iterator<Vertex> iter = VminusS.iterator(); iter.hasNext();) {
Vertex current = iter.next();
if (smallestDVertex == null || current.d < smallestDVertex.d) {
smallestDVertex = current;
}
}
for (Iterator<Vertex> iter = smallestDVertex.neighbors.iterator(); iter.hasNext();) {
Vertex neighbor = iter.next();
double edgeWt = weight[smallestDVertex.index][neighbor.index];
if (smallestDVertex.d + edgeWt < neighbor.d) {
neighbor.d = smallestDVertex.d + edgeWt;
neighbor.pred = smallestDVertex;
}
}
VminusS.remove(smallestDVertex);
}
System.out.println("Dijsktra's algorithm finished for source vertex " + source);
}
public void printShortestPath(Vertex destination, Vertex source) {
//ArrayList<Vertex> path = new ArrayList<Vertex>();
System.out.print("The shortest path from " + source + " to " + destination + " is: ");
Vertex cur = destination;
while (cur != null) {
System.out.print(cur + " -> ");
//path.add(0, cur);
cur = cur.pred;
}
//System.out.println();
}
}
顶点类：
package TestGraphs;
import java.util.ArrayList;
public class Vertex {
public String name;
public int x, y;
public boolean visited;
public double d; // used by Dijkstra's alg
public Vertex pred; // used by Dijkstra's alg
public int index;
// used for adjacency list representation:
ArrayList<Vertex> neighbors;
public Vertex(String name) {
this.name = name;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
测试等级： 包测试图
import TestGraphs.Vertex;
import java.util.Random;
public class TestGraphs {
/**
* @param args the command line arguments
*/
public static double distance(double x0, double y0, double x1, double y1) {
return Math.sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
}
public static void main(String[] args) {
// TODO code application logic here
Random r = new Random();
int source;
int numVertices = 10;
Graph g = new Graph(numVertices);
for (int i = 0; i < numVertices; i++) {
g.vertex[i] = new Vertex("Vertex " + i);
g.vertex[i].x = r.nextInt(10);
g.vertex[i].y = r.nextInt(10);
g.vertex[i].index = i;
}
for (int i = 0; i < numVertices; i++) {
for (int s = 0; s < 2; s++) {
int n = r.nextInt(numVertices);
while (n == i) {
n = r.nextInt(numVertices);
}
g.weight[i][n] = g.weight[n][i]
= distance(g.vertex[i].x, g.vertex[i].y, g.vertex[n].x, g.vertex[n].y);
}
}
// // find nearest neighbors:
// for (int i = 0; i < numVertices; i++) {
// double lowestD = Double.MAX_VALUE;
// int nearestNeighbor = 0;
// for (int j = 0; j < numVertices; j++) {
// if (i != j) {
// double d = distance(g.vertex[i].x, g.vertex[i].y,
// g.vertex[j].x, g.vertex[j].y);
// if (d < lowestD) {
// nearestNeighbor = j;
// lowestD = d;
// }
// }
// }
// // add edge between i and nearestneighbor;
// System.out.println(g.vertex[i] + " has nearest neighbor " + g.vertex[nearestNeighbor]);
// g.weight[i][nearestNeighbor] = lowestD;
// }
g.createAdjacencyLists();
g.printGraph();
g.dijkstra(g.vertex[0]);
System.out.println("vertex d values (after running Dijsktra's algorithm):");
for (int i = 0; i < g.vertex.length; i++) {
System.out.println(g.vertex[i] + " d: " + String.format("%.2f", g.vertex[i].d));
}
System.out.println();
// test some shortest paths:
source = 0;
for (int i = 0; i < numVertices; i++) {
g.printShortestPath(g.vertex[i], g.vertex[source]);
System.out.println("(distance = " + String.format("%.2f", g.vertex[i].d) + ")");
}
source = 5;
//System.out.println("BFS returns: " + g.breadthFirstSearch(g.vertex[0]));
}
}
# 1 楼答案
试着这样做：
此示例包含一些伪代码，但其思想应该很清楚