深度优先算法解决有向有权图的最短路径问题

从城市1到城市到城市3有很多条路，每条路的路况各不相同，所耗费的时间都标记在了箭头上，现在需要找出从1到3的最短路径。

有向图：意思是来回的路径值可以是不一样的

有权图：意思是每套路径的值可以是不一样的

package myalgorithm;
public class ShortPath {
    /*全局最短路径*/
    public int stepnum = 999;
    /*构建4*4路径图，-1表示此路不通*/
    int[][] graph = {
            {0 ,2 ,6 ,4},
            {-1,0 ,3 ,-1},
            {7 ,-1,0 ,1},
            {5 ,-1,12,0}
    };
    /*初始标记数组都为0*/
    public int[] mark = new int[graph.length];
   
    /*采用递归的DFS算法*/
    public void DFS(int cur, int length) {
        /*还没到3号车站，路径就已经够长了*/
        if (length>stepnum)
        {
            return;
        }
        /*到达目的地3号车站*/
        if (cur == 2)
        {
            if(length < stepnum)
            {
                stepnum = length;
            }
            return;//找到之后立即返回，不再继续
        }

        //到下一个车站，需要遍历所有的车站，看看那个车站没有走过并且路是通的
        for(int i=0;i<4;i++)
        {
            if(graph[cur][i] != -1 
                    && mark[i] == 0)
            {
                mark[i] = 1;//标记该点已经走过
                DFS(i,length+graph[cur][i]);
                mark[i] = 0;//取消该点的标记
            }
        }
        return;
    }
   public static void main(String[] args) {
        ShortPath my = new ShortPath();
        long start1 = System.currentTimeMillis();
        my.mark[0]= 1;
        my.DFS(0,0);
        long end1 = System.currentTimeMillis();
        System.out.println("DFS step: " + my.stepnum + " time:" + (end1-start1));
    }

}

深度优先算法解决有向有权图的最短路径问题

相关推荐