JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时,指定节点到所有节点的最小路径均已求出。

算法简述如下:

准备好两个辅助性数据结构:

1 ParentLength : 用来记录到当前节点之前的父节点,与到当前节点的最小路径

2 Path: 记录指定节点到所有节点的ParentLength。初始化时,所有的ParentLength的父节点都为指定的起始节点,长度都是INFINITY,代表没有联通,距离无穷大。

Path的关键算法是adjust(from,to,length),每当发现一条新的,从一个已访问的节点(from)到未访问的节点(to)之间的新路径时,Path则用其更新ParentLength列表,重新计算到那个未访问节点(to)的最新距离:以前到from节点的距离+新的距离,然后比较它与to节点对应的ParentLength老的距离之间的长度,如果新距离短,则将to节点对应的ParentLength更新为长度为新距离的,父节点为from;以此步骤保证Path总是保持当前遍历状态下,到各个节点的最短路径。

Path的另一个关键算法是getMin,它会返回到所有未访问节点中,最短的路径的那个节点。

图使用邻接矩阵法表示,关于邻接矩阵可参见:Graph 图-邻接表法

Graph.path是最小路径算法,工作方式如下:

    根据指定的起始节点初始化返回值Path对象。

将指定的起始节点标志为已访问。并设置为当前节点。

然后

1 找到当前节点所有联通的未知节点,和到这些路径长度,调用Path.adjust更新Path。

2 步骤 1 结束后,从调用Path.getMin获得到所有未访问节点中,最短的路径的那个节点。标志为访问过,并作为当前节点。

3 重复 步骤 1 步骤 2 n次(n为图中的节点数量),算法结束。

代码中的Path.print()为打印函数,为测试之用。

Path.main()提供简单测试。

  1class ParentLength {    //记载上一个节点与当前最小路径
  2    private int parent;        //上一个节点
  3    private int length;        //最小路径长度
  4    ParentLength(int parent, int length) {
  5        this.parent = parent;
  6        this.length = length;
  7    }

  8
  9    int parent() {    return parent; }
 10    int length() {    return length; }
 11}

 12
 13class Path {    //存储最小路径
 14    private ParentLength[] pls;
 15    private Graph g;    //确定指定位置的节点是否被访问过和打印时使用
 16    Path(int size, int start, Graph g) 
 17        //初始化最小路径数组,将所有最小路径的起点都置为start,并将路径长度置为INFINITY
 18        pls = new ParentLength[size];    
 19        for(int i=0; i<size; i++
 20            pls[i] = new ParentLength(start,Graph.INFINITY);
 21        this.g = g;
 22    }

 23    
 24    //根据新发现的路径调整最小路径
 25    void adjust(int from, int to, int length) {
 26        //根据上一个节点的路径,计算出新的路径长度
 27        int newLength = pls[from].length() != Graph.INFINITY? 
 28            pls[from].length() + length: length;
 29        //如果到指定节点的新路径长度小于原来的最小路径,则更新到该节点的最小路径,和其父节点
 30        if(newLength < pls[to].length()) pls[to] = new ParentLength(from,newLength);
 31    }

 32
 33    int getMin() {    //求得到当前所有未访问节点的最近的一个节点
 34        int pos = 0;
 35        for(int i=1; i<pls.length; i++)
 36            if(!g.isVisited(i) && pls[i].length() < pls[pos].length()) pos = i;
 37        return pos;
 38    }

 39
 40    void print() {    //打印
 41        for(int i=0; i<pls.length; i++{
 42            int current = i;    
 43            System.out.print((pls[current].length() == Graph.INFINITY? "INFINITY": pls[current].length()) + "  " );
 44            do {
 45                System.out.print(g.get(current) + " <-- ");
 46                current = pls[current].parent();    
 47            }
 while(current != pls[current].parent());
 48            System.out.println(g.get(current));
 49        }

 50    }

 51}

 52
 53class Vertex //顶点,记载数据value,并记载是否访问过
 54    private Object value;
 55    private boolean isVisited;
 56    Vertex(Object value) {
 57        this.value = value;
 58    }

 59
 60    void visit() { isVisited = true; }
 61    void clean() {    isVisited = false; }
 62    boolean isVisited() return isVisited; }
 63    Object value() return value; }
 64    @Override public String toString() {    return "" + value; }
 65}

 66
 67class Graph {
 68    private Vertex[] vertexs;
 69    private int[][] adjMat;
 70    private int length = 0;
 71    static final int INFINITY = ~(1<<31);    //整数的最大值,表示没有路径
 72
 73    Graph(int size) {    //初始化
 74        vertexs = new Vertex[size];
 75        adjMat = new int[size][size];
 76        for(int i=0; i<size; i++)    //将邻接矩阵初始化为全部不通
 77            for(int j=0; j<size; j++)
 78                adjMat[i][j] = INFINITY;
 79    }

 80
 81    void add(Object value) {    //添加顶点
 82        assert length <= vertexs.length;
 83        vertexs[length++= new Vertex(value);
 84    }

 85
 86    void connect(int from, int to, int length) {
 87        adjMat[from][to] = length;    //设置指定节点之间的有向路径
 88    }

 89
 90    /**
 91     * 在邻接矩阵中,查找指定顶点的未访问过邻居顶点
 92     * 如果从从起点到终点的边存在,且没有标志为访问,则返回终点下标。
 93     * @param offset 指定开始查找的列
 94     * @param index    指定查找的行
 95     */

 96    int findNeighbor(int index,int offset) {
 97        for(int i=offset; i<length; i++{
 98            if(adjMat[index][i] != INFINITY && !vertexs[i].isVisited()) return i;
 99        }

100        return -1;
101    }

102
103    Vertex get(int index) {    return vertexs[index];    }
104
105    Path path(int index) {    //最小路径算法
106        assert vertexs[index] != null;
107        Path result = new Path(length,index,this); //初始化Path
108        vertexs[index].visit();    //将其实节点标志为访问过
109        for(int n=1; n<length; n++{    //一共经过n此迭代就可得到最终结果
110            int i = 0;
111            while((i = findNeighbor(index,i+1)) != -1)    //寻找当前节点的所有为访问邻居
112                result.adjust(index, i, adjMat[index][i]);    //根据新路线调整最小路径
113            index = result.getMin();    //将当前节点更新为路径表中为访问的最近的那个节点
114            vertexs[index].visit();    //将当前节点标志为访问过;
115        }

116        clean();
117        return result;
118    }

119
120    boolean isVisited(int index) return vertexs[index].isVisited(); }
121
122    void clean() for(Vertex v: vertexs) if(v != null)v.clean(); }
123
124    public static void main(String[] args) {
125        Graph g = new Graph(20);
126        //添加节点
127        g.add('a');
128        g.add('b');
129        g.add('c');
130        g.add('d');
131        g.add('e');
132        //添加有向有权边
133        g.connect(0,1,50);
134        g.connect(0,3,80);
135        g.connect(1,2,60);
136        g.connect(1,3,90);
137        g.connect(2,4,40);
138        g.connect(3,2,20);
139        g.connect(3,4,70);
140        g.connect(4,1,50);
141        Path p = g.path(0);    //获得最小路径
142        p.print();    //打印
143    }

144}
posted on 2008-05-28 15:39 rogerfan 阅读(806) 评论(0)  编辑  收藏 所属分类: 【JAVA算法】

只有注册用户登录后才能发表评论。


网站导航: