×

关注微信公众号

免备案网站空间虚拟主机双线空间域名查询PS数码后期
photoshop互助课堂数百G视频教程下载英语培训机构初中英语如何学随时随地聆听大师开讲/课堂
酷素材!视频教程打包下手绘教程抠图教程路径专辑photoshop cs3视频教程
查看: 2614|回复: 10

[C & C++] 程序是用优先队列写的dijstra算法,求费用限制下的距离最短路径,求大侠修改局部

[复制链接]
发表于 2011-1-15 11:22:47 | 显示全部楼层 |阅读模式
这个程序是用优先队列写的dijstra算法,求费用限制下的距离最短路径,但该程序只求出最短距离,却没有显示出相应的最短路径,小弟才学有限,忘各位大侠帮忙修改一下,能显示最短路径
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 110
#define INF 1 << 29
using namespace std;

struct Node
{
     int id,dis,c;
     friend bool operator <(const Node &a,const Node &b)
{
    if(a.dis!=b.dis)
         return a.dis>b.dis;
     else
     return a.c>b.c;
}
};

int n,m,cmax;
int d[MAXN];
vector <Node> map[MAXN];

int dijkstra(int s)
{
     priority_queue<Node> p_q;    /* 优先级队列*/

     Node e={s,0,0},ne;
     int i,k,tmp,tc;

     d[s]=0;
     p_q.push(e);

     while(!p_q.empty())
     {
         e=p_q.top(); /* 每次筛出来的都是具有最小距离的边 */
         p_q.pop();
         d[e.id]=e.dis;
         if(e.id==n)
             return d[n];
         for(i=0;i<map[e.id].size();i++)   /* 对于和这个点相邻的邻边 */
         {
             k=map[e.id][i].id;
             tmp=e.dis+map[e.id][i].dis;
             tc=e.c+map[e.id][i].c;
             if(tc<=cmax) //总代价满足要求,不用判断!visit[i]&&tmp<d[k]
             {
                 ne.id=k;
                 ne.dis=tmp;
                 ne.c=tc;
                 p_q.push(ne);
             }
     }
}
if(d[n]!=INF)
     return d[n];
else
     return -1;
}

int main()
{
   
   
     int i,j;
     int from,to,dis,cost;
     Node temp;
   
     printf("输入时间的限制权值:\n");
     while(scanf("%d",&cmax)!=EOF)
     {
         printf("输入图的顶点数和边数:\n");
         scanf("%d",&n);
         scanf("%d",&m);
         for(i=1;i<=n;i++)
         {
             map[i].clear();
             d[i]=INF;
         }

         printf("输入起点,终点,费用权值,时间权值:\n");

         for(i=0;i<m;i++)
         {
             scanf("%d %d %d %d",&from,&to,&dis,&cost);
             temp.id=to;
             temp.dis=dis;
             temp.c=cost;
             map[from].push_back(temp);
         }
         printf("%d\n",dijkstra(1));  
     }
     return 0;  
}
本帖的地址:http://bbs.jcwcn.com/forum.php?mod=viewthread&tid=346072
跟着教程做一遍,做完的图要到这里评论交作业,教程有看不懂的地方,可以在贴子下面评论
发表于 2018-6-6 12:12:42 | 显示全部楼层
酷素材
好帖就是要顶
回复 支持 反对

使用道具 举报

发表于 2018-6-6 11:38:14 | 显示全部楼层
真心顶。。。。
回复 支持 反对

使用道具 举报

发表于 2018-6-6 11:35:23 | 显示全部楼层
很好哦。。。
回复 支持 反对

使用道具 举报

发表于 2018-6-6 11:58:04 | 显示全部楼层
酷素材
不错不错
回复 支持 反对

使用道具 举报

发表于 2018-6-6 12:24:29 | 显示全部楼层
酷素材
教程网我挺你
回复 支持 反对

使用道具 举报

发表于 2018-6-11 09:04:44 | 显示全部楼层
好帖就是要顶
回复 支持 反对

使用道具 举报

发表于 2018-6-11 09:39:03 | 显示全部楼层
真心顶。。。。
回复 支持 反对

使用道具 举报

发表于 2018-6-11 09:25:33 | 显示全部楼层
难得一见的好帖
回复 支持 反对

使用道具 举报

发表于 2018-6-11 09:03:40 | 显示全部楼层
LZ真是人才
回复 支持 反对

使用道具 举报

发表于 2018-6-11 09:45:31 | 显示全部楼层
好帖子要收藏
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | [立即注册]

本版积分规则

2345