Java开发网 - 请各位高手指点我一个程序，关于用Dijkstra 求无相图的最短路径。

Java开发网

您没有登录

» Java开发网 » Java SE 综合讨论区 » 编程/算法/API

打印话题 寄给朋友 订阅主题

作者

请各位高手指点我一个程序，关于用Dijkstra 求无相图的最短路径。

jeffwang

发贴: 3
积分: 0

于 2008-10-30 22:05

因为是无向图，因此结点5和结点0之间应该是有路径，可最后结果输出确实两者之间无路径，请高手指点，小弟我不甚感激。以下是我的原代码。
//undirected graphic 无向图
import java.util.ArrayList;

public class Dijkstra {
static ArrayList<Edge> graph = null;

static ArrayList<Integer> S = null;

static ArrayList<Integer> V = null;

static Edge[] ww = null;

public static void main(String[] args){
int[] nodes = { 0, 1, 2, 3, 4, 5, 6 };
graph = new ArrayList<Edge>();
graph.add(new Edge(0, 1, 20));
graph.add(new Edge(0, 3, 50));
graph.add(new Edge(0, 4, 100));
graph.add(new Edge(1, 2, 60));
graph.add(new Edge(2, 4, 15));
graph.add(new Edge(3, 2, 40));
graph.add(new Edge(3, 4, 60));
graph.add(new Edge(4, 5, 50));
graph.add(new Edge(3, 5, 10));
graph.add(new Edge(5, 6, 30));
graph.add(new Edge(6, 3, 90));
Initialization(nodes[5],nodes[0],nodes);// 起始点是5，终点是0
//i means the value of the node1
} // end main

public static void Initialization(int node1,int node2,int nodes[]){
S = new ArrayList<Integer>();
S.add(node1); // input the start of the nodes

V = new ArrayList<Integer>();
for (int w = 0; w < nodes.length; w++)
if(nodes[w]!=node1)
V.add(nodes[w]);

//initialze the parent of its node and its weight ,if there is no connection , then the weight=-1
int m=2*nodes.length;

ww = new Edge[m-1];
ww[0] = new Edge(-1, node1,0);

for (int w = 0; w <V.size(); w++){
int n =V.get Wilted Rose

;
ww[w + 1] = new Edge(node1, n, getWeight(node1, n));
}

for(int w=0 ;w<V.size();w++){
int n =V.get Wilted Rose

;
ww[w+7] = new Edge(n,node1, getWeight(n, node1));
}

//to find the node that has the smallest weight,and add it to the S.
while(V.size()>0) {
Min tt = getMinWeightNode();
if(tt.getWeight()==-1) // no conncetion
tt.Path(node1,node2);
else
tt.Path(node2);

int node = tt.getLastNode();
S.add(node);
setWeight(node);
}
}

//find a parent node
public static int getParent(Edge[] parents, int node){
if (parents != null) {
for (Edge nd : ww){
if (nd.getBenode() == node){
return nd.getPreNode();
}
if (nd.getPreNode()==node){
return nd.getBenode();
}
}
}
return -1;
}

public static void setWeight(int preNode){
if (graph != null && ww != null &&V != null) {
for (int node :V){
Min msp=getShortPath(node);
int w1 = msp.getWeight();
if (w1 == -1)
continue;
for (Edge n : ww){
if (n.getBenode() == node){
if (n.getWeight() == -1 || n.getWeight() > w1){
n.setWeight(w1);
n.setPreNode(preNode);
break;
}
}
if (n.getPreNode() == node){
if (n.getWeight() == -1 || n.getWeight() > w1){
n.setWeight(w1);
n.setBenode(preNode);
break;
}
}
}
}
}
}
//to get the weights between two nodes
public static int getWeight(int preNode, int node){
if (graph != null){
for (Edge s : graph){
if (s.getPreNode() == preNode && s.getBenode() == node)
return s.getWeight();
if (s.getPreNode() == node && s.getBenode() == preNode)
return s.getWeight();
}

}
return -1;
}

// to find a node that has smallest weight in V.
public static Min getMinWeightNode(){
Min minMsp = null;
if (V.size() > 0){
int index = 0;
for (int j = 0; j <V.size(); j++) {
Min msp = getShortPath(V.get(j));
if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) {
minMsp = msp;
index = j;
}
}
V.remove(index);

}
return minMsp;
}

//to find a shortest path of a node
public static Min getShortPath(int node) {
Min mm = new Min(node);
if (ww != null &&S != null) {
for (int i = 0; i < S.size(); i++){
Min tempMsp = new Min(node);
int parent = S.get Light Bulb

;
int currentNode = node;
while (parent > -1){
int weight = getWeight(parent, currentNode);
if (weight > -1) {
tempMsp.addNode(parent);
tempMsp.addWeight(weight);
currentNode = parent;
parent = getParent(ww, parent);
} else
break;
}

if (mm.getWeight() == -1 || tempMsp.getWeight()!=-1 && mm.getWeight() > tempMsp.getWeight())
mm = tempMsp;
}
}

return mm;
}
}

class Edge {
private int preNode;

private int benode;

private int weight;

public Edge(int preNode, int benode, int weight) {
this.preNode = preNode;
this.benode = benode;
this.weight = weight;
}

public int getPreNode(){
return preNode;
}

public void setPreNode(int preNode){
this.preNode = preNode;
}

public int getBenode() {
return benode;
}

public void setBenode(int benode){
this.benode = benode;
}

public int getWeight(){
return weight;
}

public void setWeight(int weight){
this.weight = weight;
}

}

//pursue the shortest path
class Min {
private ArrayList<Integer> List;

private int weight;

public Min(int node) {
List = new ArrayList<Integer>();
List.add(node);
weight = -1;
}
public int getFirstNode(){
int size=List.size();
return List.get(0);
}
public ArrayList<Integer> getNodeList(){
return List;
}

public void setNodeList(ArrayList<Integer> nodeList) {
List = nodeList;
}

public void addNode(int node) {
if (List == null)
List = new ArrayList<Integer>();
List.add(0, node);
}

public int getLastNode(){
int size = List.size();
return List.get(size - 1);

}

public int getWeight(){
return weight;
}

public void setWeight(int weight){
this.weight = weight;
}

public void Path(int node2){
Path(-1,node2);

}

public void Path(int Node,int node2){
String result = "[";
if (Node != -1)
List.add(Node);
for (int i=0; i < List.size(); i++){
result += "" +List.get Light Bulb

;
if (i < List.size() - 1)
result += ",";
}
result += "]:" + weight;
if(List.get(0)==node2||List.get(List.size()-1)==node2)
System.out.println(result);
}

public void addWeight(int w){
if (weight == -1)
weight = w;
else
weight += w;
}
}

话题树型展开

人气	标题	作者	字数	发贴时间
9427	请各位高手指点我一个程序，关于用Dijkstra 求无相图的最短路径。	jeffwang	5606	2008-10-30 22:05
7517	Re:请各位高手指点我一个程序，关于用Dijkstra 求无相图的最短路径。	JiafanZhou	52	2008-11-10 19:10

已读帖子

新的帖子

被删除的帖子