dfs 与 dijkstra 总结

Dijkstra:

//寻求加权图起始点到各个节点的最短路径

for i <- 1:n

         do distance[i] <- INF;

distance[0] <- 0;//起始节点距离为0

 

minDistance <- INF;//最短距离

presentNode <- -1;

 

for i <- 1:n

         if !known[i] && distance[i]<minDistance

                   presentNode <- i;

                   minDistance <-distance[i];

 

if presentNode == -1//未找到最短距离且未知节点

         return;

 

known[presentNode] <- 1;//将该节点标为已知

for i<- 1:n

         if adjacent(i, presentNode)//节点相邻

                   if distance[i] > distance[presentNode] + length(i, presentNode)

                   //更新节点距离

                            distance[i] = distance[presentNode] + length(i, presentNode);

////////////////////////////////////////////////////////////////////////////////

Dfs

//深度优先搜索

known[presentNode] <- 1;

 

if presentNode == destinationNode

         return;

 

if distance > destinationDistace//加距离超出或者类似的条件，剪枝

         return;

 

for i <- 1:n

         if adjacent(presentNode, i) && known[i]

                   DFS(i);

                   known[i] = 0;