计算机科学论坛--张铭《数据结构与算法》书中Dijkstra算法的变形以及另外一种思路

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

>>计算机科学论坛<<

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 张铭《数据结构与算法》书中Dijkstra算法的变形以及另外一种思路

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 8280 个阅读者　　

*	贴子主题：张铭《数据结构与算法》书中Dijkstra算法的变形以及另外一种思路	举报打印推荐 IE收藏夹
	本主题类别:

chyl

  等级：大一(高数修炼中)
  文章：12
  积分：120
  门派：XML.ORG.CN
  注册：2006/8/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

张铭《数据结构与算法》书中Dijkstra算法的变形以及另外一种思路

一、Dijkstra算法的变形，只写出主体部分，其它与书上一样，希望对大家能有所启发。
int ShortestPath_Dijkstra(Graphm &G,int start,int end)           //start为起点,end为终点
{
    Dist *D=new Dist[G.VerticesNum()];
    for(int i=0;i<G.VerticesNum();i++)
    {
        D[i].index=i;
        D[i].length=999;                                         //999代表Infinity
        D[i].pre=start;
    }
    D[start].length=0;
    MinHeap<Dist> H(G.numEdge);                        //最坏情况下，需要遍历所有的边
    H.insert(D[start]);
    while(!H.IsEmpty())
    {
        Dist d;
        d=H.RemoveMin();
        if(G.Mark[d.index]==1) continue;         //如果此定点已经是最短路径,则不必访问
        G.Mark[d.index]=1;
        for(Edge e=G.FirstEdge(d.index);G.IsEdge(e);e=G.NextEdge(e))
        {
            if(D[G.ToVertex(e)].length>D[d.index].length+e.weight)
            {
                D[G.ToVertex(e)].length=D[d.index].length+e.weight;
                D[G.ToVertex(e)].pre=d.index;
                H.insert(D[G.ToVertex(e)]);
            }
        }
    }
    return D[end].length;
}
二、分支界限法解决单源最短路径问题，看似和Dijkstra的原理一样，是用的贪心法。请大家看看有没有道理。
int ShortestPath_Dijkstra(Graphm &G,int start,int end)           //start为起点,end为终点
{
    int ShortestLength=999;
    Dist *D=new Dist[G.VerticesNum()];
    for(int i=0;i<G.VerticesNum();i++)
    {
        D[i].index=i;
        D[i].length=999;
        D[i].pre=start;
    }
    D[start].length=0;
    MinHeap<Dist> H(G.numEdge);                  //最坏情况下，需要遍历所有的边
    H.insert(D[start]);
    while(!H.IsEmpty())
    {
        Dist d;
        d=H.RemoveMin();
        if(G.Mark[d.index]==1) continue;
        G.Mark[d.index]=1;
        for(Edge e=G.FirstEdge(d.index);G.IsEdge(e);e=G.NextEdge(e))
        {
            if(ShortestLength>d.length+e.weight && G.Mark[G.ToVertex(e)]==0)
            {
                D[G.ToVertex(e)].length=d.length+e.weight;   //也不一定是最优的，但由于在搜索中可以剪枝，所以效率也比较高。
                D[G.ToVertex(e)].pre=d.index;
                H.insert(D[G.ToVertex(e)]);
            }
        }
    }
    return D[end].length;
}

   收藏   分享
顶(1)

2006/8/11 0:54:00

afen_pku

  等级：大二(研究C++)
  文章：21
  积分：214
  门派：XML.ORG.CN
  注册：2006/5/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

呵呵，不错哈

2006/8/11 10:24:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第3楼

第一个,我觉得跟书上是一样的,没本质上的区别,书上也是判断了是不是visited,如果是visited然后就放弃了.
另外书上的算法可以保证最后一次运行完后,heap里的东西直接丢弃,而你的似乎要运行到heap为空.
第2个没怎么看懂,shortestLength 代表什么? 为什么一直保持999?
另外这样算似乎本身就是错误的,因为后面的值如果比较大,而点还没有访问,那么大的一样可以覆盖小的,简单的说,就是你把D[G.ToVertex(e)].length>D[d.index].length+e.weight这个条件给省去了~

2006/8/11 14:05:00

chyl

  等级：大一(高数修炼中)
  文章：12
  积分：120
  门派：XML.ORG.CN
  注册：2006/8/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第4楼

呵呵感谢carroty的意见，是这样的，
    第一个就是Dijkstra的变形，本质上没有区别。我这样写的目的是为了突出它的周游框架，我认为动态规划算法是穷举法的一个进化，但都是建立在周游全部问题的解空间树基础上的。只不过动态规划算法牺牲了空间来储存已经计算过的节点以避免重复节点的计算。所以我的算法就写成了经典的光度优先周游的框架。这样比较容易理解和记忆一些。
    书上的Dijkstra算法，外层循环是for(i=0;i<G.VerticesNum();i++)，i的作用是单纯的计数器，不代表图中的一个点，我当时看得很头疼。下面找UNVISITED点的时候代码较长，没有必要，一个continue就可以解决。
第二个，很抱歉我在编辑帖子的时候漏掉了一句。我现在重新放进来。
int ShortestPath_Dijkstra(Graphm &G,int start,int end)           //start为起点,end为终点
{
    int ShortestLength=999;
    Dist *D=new Dist[G.VerticesNum()];
    for(int i=0;i<G.VerticesNum();i++)
    {
        D[i].index=i;
        D[i].length=999;
        D[i].pre=start;
    }
    D[start].length=0;
    MinHeap<Dist> H(G.numEdge);                  //最坏情况下，需要遍历所有的边
    H.insert(D[start]);
    while(!H.IsEmpty())
    {
        Dist d;
        d=H.RemoveMin();
        if(G.Mark[d.index]==1) continue;
        G.Mark[d.index]=1;
        for(Edge e=G.FirstEdge(d.index);G.IsEdge(e);e=G.NextEdge(e))
        {
            if(ShortestLength>d.length+e.weight && G.Mark[G.ToVertex(e)]==0)
            {
                D[G.ToVertex(e)].length=d.length+e.weight;
                D[G.ToVertex(e)].pre=d.index;
                H.insert(D[G.ToVertex(e)]);
                if(G.ToVertex(e)==end)                                   //漏掉的代码
                    ShortestLength=d.length+e.weight;              //漏掉的代码
            }
        }
    }
    return D[end].length;
}
      这种算法是没有D[G.ToVertex(e)].length>D[d.index].length+e.weight这句条件判断的，因为那样就变成了动态规划了，这种算法用的仍然是广度优先周游问题的解空间树，但是是比Dijkstra更贪婪的算法。因为它每次选择的都是当前距离起点最短的长度的节点(因为是从堆顶得到的)，所以它第一次得到的shortestLength不一定是最短的，还要继续进行。这时候shortestLength可以作为解的上界，如果某个未到达终点的顶点已经比shortestLength大了，那么就没必要继续周游下去。
    这种算法思路比较简单，容易想到，如果考试的时候想不出来动态规划的又不想用穷举法，那就用这种方法，虽然比动态规划慢一些但是绝对比穷举法的O(2^n)要好。所以就写出来了呵呵。仅供参考。

2006/8/11 20:33:00

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第5楼

还是错呀！
例如：G={<a,b,1>,<a,c,2>,<b,d,3>,<c,d,100>,<d,e,10>} start=a,end=e你这个算的结果是112

另外（1）如果非连通图。。。（2）书上该算法有问题，你的算法也有和它一样的问题

2006/8/11 21:03:00

chyl

  等级：大一(高数修炼中)
  文章：12
  积分：120
  门派：XML.ORG.CN
  注册：2006/8/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第6楼

我刚才用你的例子编译运行了一遍，两个程序得到的结果都是14呀。
而且，该算法不支持非连通图，张铭老师的视频里说了，我也觉得没有必要吧。

2006/8/11 22:40:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第7楼

不错,懂了~
:)
如果用哪个n的循环,则对非连通图也没问题,反正肯定会在n次循环只内跑完,用while循环的可能多跑一会,也是可以跑完的,不能到达的点,最后得到的值是无穷.

2006/8/12 11:33:00

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第8楼

呵呵，是，两个都是14。
算完后D数组的pre变成啥了？以我的例子，d的pre为c，这时打印一下这条路：a，c，d，e，长为14，对吧？我昨天没仔细看你的return处，如果是那样return建议就不要有pre了。有的话也可以，在每次出堆时再更新一下D数组就可以了。
教材上的算法不能处理非连通图，但是只要加1句就可以了，就是在出堆时加上：if(d.length==INFINITY) return"非连通"；而你这个是不能这样做的，就是说你这个是修改不成能够判断非连通的。
教材上的算法在动态判断时的&&G.Mark[G...]=UNVISITED是不必要的，即没有这句也可以。同样，我认为 && G.Mark[G.ToVertex(e)]==0也是不必要的，你可以去掉它试试。
以上为我对你的算法的理解，请指教！

2006/8/12 15:04:00

chyl

  等级：大一(高数修炼中)
  文章：12
  积分：120
  门派：XML.ORG.CN
  注册：2006/8/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第9楼

呵呵受教了：）
Supremgoooo讲的很有道理，D数组的pre应该是被存放到堆里了，这个堆中可能会有两个   D[i]，但D[i]的pre不同，所以必须利用指针找到堆中的D[i]。修改后的代码可以输出最短路径如下：
int ShortestPath_Dijkstra(Graphm &G,int start,int end)           //start为起点,end为终点
{
    int ShortestLength=999;
    Dist *D=new Dist[G.VerticesNum()];
    for(int i=0;i<G.VerticesNum();i++)
    {
        D[i].index=i;
        D[i].length=999;
        D[i].pre=start;
    }
    D[start].length=0;
    MinHeap<Dist> H(G.numEdge);                  //最坏情况下，需要遍历所有的边
    H.insert(D[start]);
    while(!H.IsEmpty())
    {
        Dist d;
        d=H.RemoveMin();
        if(G.Mark[d.index]==1) continue;
        G.Mark[d.index]=1;
        for(Edge e=G.FirstEdge(d.index);G.IsEdge(e);e=G.NextEdge(e))
        {
            cout<<"Current: "<<d.index<<endl;
            if(ShortestLength>d.length+e.weight && G.Mark[G.ToVertex(e)]==0)
            {
                D[G.ToVertex(e)].length=d.length+e.weight;
                D[G.ToVertex(e)].pre=d.index;
                H.insert(D[G.ToVertex(e)]);
                if(G.ToVertex(e)==end)
                    ShortestLength=d.length+e.weight;
            }
        }
    }
    cout<<"Shortest Path: ";          //输出最短路径
    Dist* temp=&D[end];
    while(temp->length!=0)
    {
        cout<<temp->index<<" ";
        temp=&D[temp->pre];
    }
    cout<<temp->index<<endl;
    return D[end].length;
}
这个算法是宽度优先周游，那么如果仿照书上宽度优先周游森林的例子，也可以写出相应的访问非连通的算法，就是加一个外层循环就可以了。
教材上的算法在动态判断时的 G.Mark[G...]=UNVISITED是不必要的，因为如果满足了第一个条件，那么这个点肯定是UNVISITED的。对于这里则不是，我来举一个例子。
G={<a,b,10>,<b,d,100>,<a,c,20>,<c,b,30>} start=a,end=d.
首先访问b，将b插入堆中,由于b(10)是最短长度，再将b从堆顶取出并将其标记为VISITED，然后访问d的ShortestLength=110。
按照广度优先周游将c(20)插入堆中，同理将其从堆顶取出，再访问b的时候满足第一个条件，但是b已经是VISITED所以就不必访问直接将其放弃达到了提高效率的作用。
所以这条语句还是有用的，但是不可否认如果不是Dijkstra他老人家证明了的话，我也写不出来的，去掉它就是纯的分支界限法了！

2006/8/12 21:36:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/4/26 1:31:44

本主题贴数9，分页： [1]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	125.000ms