在用Dijkstra算法求解带权有向图的最短路径问题时,要求图中每条边所带的权值必须是:()
A.非零
B.非整
C.非负
D.非正
A.非零
B.非整
C.非负
D.非正
A、V1,V2,V3,V4,V7,V6,V5
B、V1,V5,V4,V7,V6,V2,V3
C、V1,V5,V6,V4,V7,V2,V3
D、V1,V5,V4,V7,V6,V3,V2
①从最西端城市出发,单向从西向东途经若干城市到达最东端城市,再单向从东向西飞回起点(可途经若干城市).
②除起点城市外,任何城市只能访问1次.
算法设计:对于给定的航空图,试设计一个算法,找出一条满足要求的最佳航空旅行路线.
数据输入:由文件input.txt提供输入数据.文件第1行有两个正整数N和V,N表示城市数(N<100),V表示直飞航线数.接下来的N行中的每行是一个城市名,可乘飞机访问这些城市.城市名出现的顺序是从西向东.也就是说,设i、j是城市表列中城市出现的顺序,当i>j时,表示城市i在城市j的东边,而且不会有两个城市在同一条经线上.城市名是一个长度不超过15的字符串,串中的字符可以是字母或阿拉伯数字,如AGR34或BEL4.
再接下来的V行中,每行有2个城市名,中间用空格隔开,如city1city2表示city1到city2有一条直通航线,从city2到city1也有一条直通航线.
结果输出:将最佳航空旅行路线输出到文件output.txt.文件第1行是旅行路线中所访问的城市总数M.接下来的M+1行是旅行路线的城市名,每行写一个城市名.首先是起点城市名,然后按访问顺序列出其他城市名.注意,最后一行(终点城市)的城市名必然是起点城市名.如果问题无解,则输出“NoSolution!”.
A、d,e,f
B、e,d,f
C、f,d,e
D、f,e,d
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!