代码如下,在58行报数组越界错误,不知道怎么办了,本来对这个算法就不太明白,求大神解决一下。
package com.andy.graphics;import javax.swing.JFrame;
import javax.swing.JOptionPane;@SuppressWarnings("serial")
public class MyGrapics extends JFrame {
private static final int MAX = -1;
static String[] vex; //顶点数组
static int vexNum, arcNum; //顶点数目和弧数目
static int[][] adjMatrix; //邻接矩阵
public static void main(String[] args) {
MyGrapics mg = new MyGrapics();
showMatrix(mg);
String inV = JOptionPane.showInputDialog("请输入起点:");
showAllPath(mg, inV);
}
//计算所有最短路径长
public static void showAllPath(MyGrapics mg, String v) {
String mas = "";
int start = locateVex(v);
for(int i=0; i<MyGrapics.vexNum; i++) {
mas += v+"到"+vex[i]+"的最短距离是:"+dijkstra(mg.adjMatrix, start, i);
mas += "\n";
}
JOptionPane.showMessageDialog(null, mas);
}
//迪杰斯特拉算法
public static int dijkstra(int[][] W1, int start, int end) {
boolean[] isLabel = new boolean[W1[0].length];// 是否标号
int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈
int i_count = -1;//栈的顶点
int[] distance = W1[start].clone();// v0到各点的最短距离的初始值
int index = start;// 从初始点开始
int presentShortest = 0;//当前临时最短距离
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
isLabel[index] = true;
while (i_count<W1[0].length) {
// 第一步:标号v0,即w[0][0]找到距离v0最近的点
int min = Integer.MAX_VALUE;
for (int i = 0; i < distance.length; i++) {
if (!isLabel[i] && distance[i] != -1 && i != index) {
// 如果到这个点有边,并且没有被标号
if (distance[i] < min) {
min = distance[i];
index = i;// 把下标改为当前下标
}
}
}
if (index == end) {//已经找到当前点了,就结束程序
break;
}
isLabel[index] = true;//对点进行标号
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
if (W1[indexs[i_count - 1]][index] == -1
|| presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {
// 如果两个点没有直接相连,或者两个点的路径大于最短路径
presentShortest = distance[index];
} else {
presentShortest += W1[indexs[i_count - 1]][index];
}
// 第二步:将distance中的距离加入vi
for (int i = 0; i < distance.length; i++) {
// 如果vi到那个点有边,则v0到后面点的距离加
if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达,则现在可达了
distance[i] = presentShortest + W1[index][i];
} else if (W1[index][i] != -1
&& presentShortest + W1[index][i] < distance[i]) {
// 如果以前可达,但现在的路径比以前更短,则更换成更短的路径
distance[i] = presentShortest + W1[index][i];
}
}
}
//如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径
return distance[end] - distance[start];
} //输出邻接矩阵
public static void showMatrix(MyGrapics mg) {
String massege = "邻接矩阵,-1表示两顶点无连接!";
massege += "\n";
for(int i=0; i<MyGrapics.vex.length; i++) {
for(int j=0; j<MyGrapics.vex.length; j++) {
massege += adjMatrix[i][j]+" ";
}
massege += "\n";
}
JOptionPane.showMessageDialog(null, massege);
}
//定位顶点位置
public static int locateVex(String vexs) {
for(int i=0; i<vexNum; i++) {
if(vexs.equals(vex[i]))
return i;
}
return -1;
}
//构造带权图
public MyGrapics() {
vexNum = Integer.parseInt(JOptionPane.showInputDialog("请输入一共有几个顶点"));
arcNum = Integer.parseInt(JOptionPane.showInputDialog("请输入一共有多少条弧"));
vex = new String[vexNum];
String vexs = JOptionPane.showInputDialog("输入所有顶点集合,逗号分隔");
String[] aVex = vexs.split(",");
for(int i=0; i<vexNum; i++) {
vex[i] = aVex[i];
}
//初始化邻接矩阵
adjMatrix = new int[vexNum][vexNum];
for(int i=0; i<vexNum; i++) {
for(int j=0; j<vexNum; j++) {
adjMatrix[i][j] = MAX;
}
}
//定义弧及权值
for(int i=0; i<arcNum; i++) {
String inW = JOptionPane.showInputDialog("请输入第"+(i+1)+"条弧的两顶点和权值(逗号分隔):");
String[] inws = inW.split(",");
String v1 = inws[0];
String v2 = inws[1];
int weight = Integer.parseInt(inws[2]);
if(locateVex(v1)!=-1 && locateVex(v2)!=-1) {
adjMatrix[locateVex(v1)][locateVex(v2)] = weight;
adjMatrix[locateVex(v2)][locateVex(v1)] = weight;
}
else {
System.out.println("无这个顶点,检查重新输入");
i--;
}
}
}
}
package com.andy.graphics;import javax.swing.JFrame;
import javax.swing.JOptionPane;@SuppressWarnings("serial")
public class MyGrapics extends JFrame {
private static final int MAX = -1;
static String[] vex; //顶点数组
static int vexNum, arcNum; //顶点数目和弧数目
static int[][] adjMatrix; //邻接矩阵
public static void main(String[] args) {
MyGrapics mg = new MyGrapics();
showMatrix(mg);
String inV = JOptionPane.showInputDialog("请输入起点:");
showAllPath(mg, inV);
}
//计算所有最短路径长
public static void showAllPath(MyGrapics mg, String v) {
String mas = "";
int start = locateVex(v);
for(int i=0; i<MyGrapics.vexNum; i++) {
mas += v+"到"+vex[i]+"的最短距离是:"+dijkstra(mg.adjMatrix, start, i);
mas += "\n";
}
JOptionPane.showMessageDialog(null, mas);
}
//迪杰斯特拉算法
public static int dijkstra(int[][] W1, int start, int end) {
boolean[] isLabel = new boolean[W1[0].length];// 是否标号
int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈
int i_count = -1;//栈的顶点
int[] distance = W1[start].clone();// v0到各点的最短距离的初始值
int index = start;// 从初始点开始
int presentShortest = 0;//当前临时最短距离
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
isLabel[index] = true;
while (i_count<W1[0].length) {
// 第一步:标号v0,即w[0][0]找到距离v0最近的点
int min = Integer.MAX_VALUE;
for (int i = 0; i < distance.length; i++) {
if (!isLabel[i] && distance[i] != -1 && i != index) {
// 如果到这个点有边,并且没有被标号
if (distance[i] < min) {
min = distance[i];
index = i;// 把下标改为当前下标
}
}
}
if (index == end) {//已经找到当前点了,就结束程序
break;
}
isLabel[index] = true;//对点进行标号
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
if (W1[indexs[i_count - 1]][index] == -1
|| presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {
// 如果两个点没有直接相连,或者两个点的路径大于最短路径
presentShortest = distance[index];
} else {
presentShortest += W1[indexs[i_count - 1]][index];
}
// 第二步:将distance中的距离加入vi
for (int i = 0; i < distance.length; i++) {
// 如果vi到那个点有边,则v0到后面点的距离加
if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达,则现在可达了
distance[i] = presentShortest + W1[index][i];
} else if (W1[index][i] != -1
&& presentShortest + W1[index][i] < distance[i]) {
// 如果以前可达,但现在的路径比以前更短,则更换成更短的路径
distance[i] = presentShortest + W1[index][i];
}
}
}
//如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径
return distance[end] - distance[start];
} //输出邻接矩阵
public static void showMatrix(MyGrapics mg) {
String massege = "邻接矩阵,-1表示两顶点无连接!";
massege += "\n";
for(int i=0; i<MyGrapics.vex.length; i++) {
for(int j=0; j<MyGrapics.vex.length; j++) {
massege += adjMatrix[i][j]+" ";
}
massege += "\n";
}
JOptionPane.showMessageDialog(null, massege);
}
//定位顶点位置
public static int locateVex(String vexs) {
for(int i=0; i<vexNum; i++) {
if(vexs.equals(vex[i]))
return i;
}
return -1;
}
//构造带权图
public MyGrapics() {
vexNum = Integer.parseInt(JOptionPane.showInputDialog("请输入一共有几个顶点"));
arcNum = Integer.parseInt(JOptionPane.showInputDialog("请输入一共有多少条弧"));
vex = new String[vexNum];
String vexs = JOptionPane.showInputDialog("输入所有顶点集合,逗号分隔");
String[] aVex = vexs.split(",");
for(int i=0; i<vexNum; i++) {
vex[i] = aVex[i];
}
//初始化邻接矩阵
adjMatrix = new int[vexNum][vexNum];
for(int i=0; i<vexNum; i++) {
for(int j=0; j<vexNum; j++) {
adjMatrix[i][j] = MAX;
}
}
//定义弧及权值
for(int i=0; i<arcNum; i++) {
String inW = JOptionPane.showInputDialog("请输入第"+(i+1)+"条弧的两顶点和权值(逗号分隔):");
String[] inws = inW.split(",");
String v1 = inws[0];
String v2 = inws[1];
int weight = Integer.parseInt(inws[2]);
if(locateVex(v1)!=-1 && locateVex(v2)!=-1) {
adjMatrix[locateVex(v1)][locateVex(v2)] = weight;
adjMatrix[locateVex(v2)][locateVex(v1)] = weight;
}
else {
System.out.println("无这个顶点,检查重新输入");
i--;
}
}
}
}
e .这不是要做实验么,可是不会这个算法啊
e .这不是要做实验么,可是不会这个算法啊
网上大把材料,这个是大俗(经典)算法啦。再说,这么大段代码,没人有耐心看的啦