📄 zdlj.java
字号:
import java.awt.*;
import java.awt.event.*;
class xy{
int x;
int y;
public xy(int X, int Y){
x=X;
y=Y;
}
}
interface List{
public void insert(int i,Object obj) throws Exception;
public Object delete(int i) throws Exception;
public Object getData(int i) throws Exception;
public int size();
public boolean isEmpty();
}
class SeqList implements List{
final int defaultSize = 10;
int maxSize;
int size;
Object[] listArray;
SeqList(){
initiate(defaultSize);
}
SeqList(int size){
initiate(size);
}
public void initiate(int sz){
maxSize = sz;
size = 0;
listArray = new Object[sz];
}
public void insert(int i,Object obj) throws Exception{
if (size == maxSize){
throw new Exception("顺序表已满无法插入！");
}
if (i > size){
throw new Exception("参数错误！");
}
for(int j = size; j > i; j--){
listArray[j] = listArray[j-1];
}
listArray[i] = obj;
size++;
}
public Object delete(int i) throws Exception{
if(size == 0){
throw new Exception("顺序表已空无法删除！");
}
if (i > size-1){
throw new Exception("参数错误！");
}
Object it = listArray[i];
for(int j = i; j < size-1; j++){
listArray[j] = listArray[j+1];
}
size--;
return it;
}
public Object getData(int i) throws Exception{
if(i < 0 || i >= size){
throw new Exception("参数错误！");
}
return listArray[i];
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public int MoreDataDelete(SeqList L, Object x) throws Exception{
int i, j;
int tag = 0;
for(i = 0; i < L.size; i++){
if(x.equals(L.getData(i))){
L.delete(i);
i --;
tag = 1;
}
}
return tag;
}
}
//---------------------------------------图
class AdjMWGraph{
static final int maxWeight = 10000;
private SeqList vertices; //存储结点的顺序表
private int[][] edge; //存储边的二维数组
private int numOfEdges; //边的个数
public AdjMWGraph(int maxV){ //构造函数，maxV为结点个数
vertices = new SeqList(maxV);
edge = new int[maxV][maxV];
for(int i = 0; i < maxV; i ++){
for(int j = 0; j < maxV; j ++){
if(i == j)
edge[i][j] = 0;
else
edge[i][j] = maxWeight;
}
}
numOfEdges = 0;
}
public int getNumOfVertices(){ //返回结点个数
return vertices.size;
}
public int getNumOfEdges(){ //返回边的个数
return numOfEdges;
}
public Object getValue(int v) throws Exception{
//返回结点v的数据元素
return vertices.getData(v);
}
public int getWeight(int v1, int v2) throws Exception{
//返回边<v1,v2>的权值
if(v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size)
throw new Exception("参数v1或v2越界出错！");
return edge[v1][v2];
}
public void insertVertex(Object vertex) throws Exception{
//插入结点
vertices.insert(vertices.size, vertex);
}
public void insertEdge(int v1, int v2, int weight) throws Exception{
//插入边<v1,v2>，权值为weight
if(v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size)
throw new Exception("参数v1或v2越界出错！");
edge[v1][v2] = weight; //置边的权值
numOfEdges ++; //边的个数加1
}
public void deleteEdge(int v1, int v2) throws Exception{
//删除边<v1,v2>
if(v1 < 0 || v1 > vertices.size || v2 < 0 || v2 > vertices.size)
throw new Exception("参数v1或v2越界出错！");
if(edge[v1][v2] == maxWeight || v1 == v2)
throw new Exception("该边不存在！");
edge[v1][v2] = maxWeight; //置边的权值为无穷大
numOfEdges --; //边的个数减1
}
public int getFirstNeighbor(int v) throws Exception{
//取结点v的第一个邻接结点。若存在返回该结点的下标序号，否则返回-1
if(v < 0 || v >= vertices.size)
throw new Exception("参数v越界出错！");
for(int col = 0; col < vertices.size; col ++)
if(edge[v][col] > 0 && edge[v][col] < maxWeight)
return col;
return - 1;
}
public int getNextNeighbor(int v1, int v2) throws Exception{
//取结点v1的邻接结点v2后的邻接结点
//若存在返回该结点的下标序号，否则返回-1
if(v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size)
throw new Exception("参数v1或v2越界出错！");
for(int col = v2 + 1; col < vertices.size; col ++)
if(edge[v1][col] > 0 && edge[v1][col] < maxWeight)
return col;
return - 1;
}
}
//----------------------------------
class RowColWeight{
int row;
int col;
int weight;
public RowColWeight(int r, int c, int w){
row = r;
col = c;
weight = w;
}
public static void createGraph(AdjMWGraph g, Object[] v, int n, RowColWeight[] rc, int e) throws Exception{
for(int i = 0; i < n; i ++)
g.insertVertex(v[i]);
for(int k = 0; k < e; k ++)
g.insertEdge(rc[k].row, rc[k].col, rc[k].weight);
}
}
class Dijkstra{
static final int maxWeight = 9999;
public static void dijkstra(AdjMWGraph g, int v0, int[] distance, int path[]) throws Exception{
int n = g.getNumOfVertices();
int[] s = new int[n];
int minDis, u = 0;
for(int i = 0; i < n; i ++){
distance[i] = g.getWeight(v0, i);
s[i] = 0;
if(i != v0 && distance[i] < maxWeight)
path[i] = v0;
else
path[i] = -1;
}
s[v0] = 1;
for(int i = 1; i < n; i ++){
minDis = maxWeight;
for(int j = 0; j < n; j ++)
if(s[j] == 0 && distance[j] < minDis){
u = j;
minDis = distance[j];
}
if(minDis == maxWeight) return;
s[u] = 1;
for(int j = 0; j < n; j ++)
if(s[j] == 0 && g.getWeight(u, j) < maxWeight && distance[u] + g.getWeight(u, j) < distance[j]){
distance[j] = distance[u] + g.getWeight(u, j);
path[j] = u;
}
}
}
}
class MyCanvas extends Canvas {
int b1lag=0;
int clear=-1;
xy []zuobiao={new xy(10,250),new xy(100,100),new xy(100,185),new xy(100,340),new xy(100,425),
new xy(200,150),new xy(200,250),new xy(200,350),new xy(300,150),new xy(300,250),new xy(300,350),
new xy(400,255)
};
MyCanvas() {
setSize(500,500);
setBackground(Color.cyan);
}
public void setClear(int clear){
this.clear=clear;
}
public void paint(Graphics g2){
g2.drawString("1",10,240);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[1].x,zuobiao[1].y);g2.drawString("9",50,174);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[2].x,zuobiao[2].y);g2.drawString("7",50,220);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[3].x,zuobiao[3].y);g2.drawString("3",50,300);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[4].x,zuobiao[4].y);g2.drawString("2",50,350);
g2.drawString("2",100,90);
g2.drawLine(zuobiao[1].x,zuobiao[1].y,zuobiao[5].x,zuobiao[5].y);g2.drawString("4",150,135);
g2.drawLine(zuobiao[1].x,zuobiao[1].y,zuobiao[6].x,zuobiao[6].y);g2.drawString("2",130,145);
g2.drawLine(zuobiao[1].x,zuobiao[1].y,zuobiao[7].x,zuobiao[7].y);g2.drawString("1",110,142);
g2.drawString("3",90,185);
g2.drawLine(zuobiao[2].x,zuobiao[2].y,zuobiao[5].x,zuobiao[5].y);g2.drawString("2",113,180);
g2.drawLine(zuobiao[2].x,zuobiao[2].y,zuobiao[6].x,zuobiao[6].y);g2.drawString("7",114,200);
g2.drawString("4",100,330);
g2.drawLine(zuobiao[3].x,zuobiao[3].y,zuobiao[7].x,zuobiao[7].y);g2.drawString("11",118,350);
g2.drawString("5",100,415);
g2.drawLine(zuobiao[4].x,zuobiao[4].y,zuobiao[6].x,zuobiao[6].y);g2.drawString("11",118,390);
g2.drawLine(zuobiao[4].x,zuobiao[4].y,zuobiao[7].x,zuobiao[7].y);g2.drawString("8",124,410);
g2.drawString("6",200,140);
g2.drawLine(zuobiao[5].x,zuobiao[5].y,zuobiao[8].x,zuobiao[8].y);g2.drawString("6",230,153);
g2.drawLine(zuobiao[5].x,zuobiao[5].y,zuobiao[9].x,zuobiao[9].y);g2.drawString("5",230,193);
g2.drawString("7",200,240);
g2.drawLine(zuobiao[6].x,zuobiao[6].y,zuobiao[8].x,zuobiao[8].y);g2.drawString("4",230,220);
g2.drawLine(zuobiao[6].x,zuobiao[6].y,zuobiao[9].x,zuobiao[9].y);g2.drawString("3",230,250);
g2.drawString("8",200,340);
g2.drawLine(zuobiao[7].x,zuobiao[7].y,zuobiao[9].x,zuobiao[9].y);g2.drawString("5",230,320);
g2.drawLine(zuobiao[7].x,zuobiao[7].y,zuobiao[10].x,zuobiao[10].y);g2.drawString("6",230,350);
g2.drawString("9",300,150);
g2.drawLine(zuobiao[8].x,zuobiao[8].y,zuobiao[11].x,zuobiao[11].y);g2.drawString("4",340,195);
g2.drawString("10",300,240);
g2.drawLine(zuobiao[9].x,zuobiao[9].y,zuobiao[11].x,zuobiao[11].y);g2.drawString("2",350,260);
g2.drawString("11",290,340);
g2.drawLine(zuobiao[10].x,zuobiao[10].y,zuobiao[11].x,zuobiao[11].y);g2.drawString("5",339,310);
g2.drawString("12",400,245);
if(b1lag==1){
g2.setColor(Color.green);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[2].x,zuobiao[2].y);
g2.drawLine(zuobiao[0].x,zuobiao[0].y,zuobiao[2].x,zuobiao[2].y);
g2.drawLine(zuobiao[2].x,zuobiao[2].y,zuobiao[5].x,zuobiao[5].y);
g2.drawLine(zuobiao[5].x,zuobiao[5].y,zuobiao[9].x,zuobiao[9].y);
g2.drawLine(zuobiao[9].x,zuobiao[9].y,zuobiao[11].x,zuobiao[11].y);
}
}
}
class WinCanvas extends Frame implements ActionListener{
MyCanvas canvas;
Button b1;
WinCanvas(String t){
super(t);
canvas=new MyCanvas();
b1=new Button("最短路径");
b1.addActionListener(this);
setLayout(new FlowLayout());
add(canvas,BorderLayout.CENTER);
Panel p=new Panel();
p.add(b1);
add(p,BorderLayout.SOUTH);
setVisible(true);
setBounds(50,50,900,600);
//setBounds(20,20,500,500);
validate();
}
public void actionPerformed(ActionEvent e){
canvas.setClear(0);
canvas.b1lag=1;
canvas.repaint();
}
}
public class zdlj{
static final int maxVertices = 100;
public static void createGraph(AdjMWGraph g, Object[] v, int n, RowColWeight[] rc, int e) throws Exception{
for(int i = 0; i < n; i ++)
g.insertVertex(v[i]);
for(int k = 0; k < e; k ++)
g.insertEdge(rc[k].row, rc[k].col, rc[k].weight);
}
public static void main(String arg[]){
AdjMWGraph g = new AdjMWGraph(maxVertices);
Integer[] a = {new Integer("1"),new Integer("2"),new Integer("3"),new Integer("4"),
new Integer("5"),new Integer("6"),new Integer("7"),new Integer("8"),new Integer("9"),
new Integer("10"),new Integer("11"),new Integer("12")};
RowColWeight[] rcw = {new RowColWeight(0,1,9),new RowColWeight(0,2,7),new RowColWeight(0,3,3),
new RowColWeight(0,4,2),new RowColWeight(1,5,4),new RowColWeight(1,6,2),
new RowColWeight(1,7,1),new RowColWeight(2,5,2),new RowColWeight(2,6,7),new RowColWeight(3,7,11),
new RowColWeight(4,6,11),new RowColWeight(4,7,8),new RowColWeight(5,8,6),new RowColWeight(5,9,5),
new RowColWeight(6,8,4),new RowColWeight(6,9,3),new RowColWeight(7,9,5),new RowColWeight(7,10,6),
new RowColWeight(8,11,4),new RowColWeight(9,11,2),new RowColWeight(10,11,5)};
int n = 12, e = 21;
try{
createGraph(g,a,n,rcw,e);
int[] distance = new int[n];
int[] path = new int[n];
Dijkstra.dijkstra(g, 0, distance, path);
int x=n-1;
int y[]=new int[n];
int z=-1;
int flag=0;
while(x!=0){
switch(path[x]){
case 0 :
y[flag]=1 ;x=0;break;
case 1 :
y[flag]=2 ;x=1;break;
case 2 :
y[flag]=3 ;x=2;break;
case 3 :
y[flag]=4 ;x=3;break;
case 4 :
y[flag]=5 ;x=4;break;
case 5 :
y[flag]=6 ;x=5;break;
case 6 :
y[flag]=7 ;x=6;break;
case 7 :
y[flag]=8 ;x=7;break;
case 8 :
y[flag]=9 ;x=8;break;
case 9 :
y[flag]=10 ;x=9;break;
case 10 :
y[flag]=11 ;x=10;break;
case 11 :
y[flag]=12 ;x=11;break;
}
z++;
flag++;
}
System.out.println(
"1到12的最短路径：");
while(z>=0){
System.out.println(y[z]+" ");
z--;
}
System.out.println(12);
}
catch (Exception ex){
ex.printStackTrace();
}
//WinCanvas win=new WinCanvas();
WinCanvas win=new WinCanvas("实验端四最短路径");
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -