找出两个点之间的所有路径(原创)

　　题目：给出一张图，找出图中从起始点到目的地的所有路径？找出最近的路径

　　这个题目要实现：

　　　　　　1、无向连通图中两点间的所有路径。

　　　　　　2、路径中不能包含环路或重复的点。

　　　　　　3、找出最近的一条路径。

　　采用的是DFS，解题思路与迷宫问题，12345所有组合类似。

                    

之前想的用邻接表作为数据结构，但是邻接表需要两个类，比较麻烦，所以修改了一下，每个顶点里面包含编号和与它相连的顶点链表。

    static class Vexnode
    {
        int index;
        List<Vexnode> list;
    }

    public static void findPath(Vexnode curNode,Vexnode endNode,boolean visited[],Stack<Integer> stack)
    {
        if(curNode==null || visited[curNode.index]==true)   //假如当前点已经访问过，就返回
            return;
        stack.push(curNode.index);//当前点入栈
        visited[curNode.index]=true;//当前点已经访问
        if(curNode.index==endNode.index)//如果当前点是目标点，输出
        {
            System.out.println(getMessage(stack));
            visited[curNode.index]=false;
            stack.pop();
            return;
        }
        List<Vexnode> list=curNode.list;//当前点链表
        for(int i=0;i<list.size();i++)//对相连的每个顶点进行搜索
        {
            findPath(list.get(i), endNode, visited, stack);
        }
        visited[curNode.index]=false;//搜索完毕后弹出，标志清除
        stack.pop();
    }
    
    private static String getMessage(Stack<Integer> stack)
    {
        Iterator<Integer> iterator=stack.iterator();
        String messageString="";
        while(iterator.hasNext())
        {
            messageString+=iterator.next()+"->";
        }
        if(stack.size()==0)
            return messageString;
        return messageString.substring(0,messageString.length()-2);
    }

测试用例：

    public static void main(String[] args) {
        Vexnode v1=new Vexnode();
        v1.index=1;
        Vexnode v2=new Vexnode();
        v2.index=2;
        Vexnode v3=new Vexnode();
        v3.index=3;
        Vexnode v4=new Vexnode();
        v4.index=4;
        Vexnode v5=new Vexnode();
        v5.index=5;
        Vexnode v6=new Vexnode();
        v6.index=6;
        Vexnode v7=new Vexnode();
        v7.index=7;
        Vexnode v8=new Vexnode();
        v8.index=8;
        Vexnode v9=new Vexnode();
        v9.index=9;
        
        List<Vexnode> l1=new ArrayList<Main.Vexnode>();
        List<Vexnode> l2=new ArrayList<Main.Vexnode>();
        List<Vexnode> l3=new ArrayList<Main.Vexnode>();
        List<Vexnode> l4=new ArrayList<Main.Vexnode>();
        List<Vexnode> l5=new ArrayList<Main.Vexnode>();
        List<Vexnode> l6=new ArrayList<Main.Vexnode>();
        List<Vexnode> l7=new ArrayList<Main.Vexnode>();
        List<Vexnode> l8=new ArrayList<Main.Vexnode>();
        List<Vexnode> l9=new ArrayList<Main.Vexnode>();
        
        l1.add(v2);
        l1.add(v4);
        v1.list=l1;
        
        l2.add(v1);
        l2.add(v3);
        l2.add(v5);
        v2.list=l2;
        
        l3.add(v2);
        l3.add(v6);
        v3.list=l3;
        
        l4.add(v1);
        l4.add(v7);
        v4.list=l4;
        
        l5.add(v2);
        l5.add(v6);
        l5.add(v8);
        v5.list=l5;
        
        l6.add(v3);
        l6.add(v5);
        l6.add(v9);
        v6.list=l6;
        
        l7.add(v4);
        l7.add(v8);
        v7.list=l7;
        
        l8.add(v5);
        l8.add(v7);
        l8.add(v9);
        v8.list=l8;
        
        l9.add(v6);
        l9.add(v8);
        v9.list=l9;
        
        boolean[] visited=new boolean[10];
        Stack<Integer> stack=new Stack<Integer>();
        findPath(v1, v9, visited, stack);
    }

输出：

1->2->3->6->5->8->9
1->2->3->6->9
1->2->5->6->9
1->2->5->8->9
1->4->7->8->5->2->3->6->9
1->4->7->8->5->6->9
1->4->7->8->9

 最短路径算法  参考：

 dijkstra算法

 dijkstra算法 JAVA实现

 dijkstra算法