图论最短路之spfa

发布时间:2021-06-24 04:59:06

#include
#include
#include
#include
using namespace std ;
const int INF = 1000000 ;
const int maxn = 10 ;
struct ArcNode
{
int to ;
int weight ;
ArcNode *next ;
};
queue Q ;
int n ;
ArcNode *List[ maxn ] ;
int inq[ maxn ] ;
int dist[ maxn ] , path[ maxn ] ;
void SPFA( int src )
{
int i , u ;
ArcNode * temp ;
for( i = 0 ; i < n ; i++ )
{
dist[ i ] = INF ;
path[ i ] = src ;
inq[ i ] = 0 ;
}
dist[ src ] = 0 ;
path[ src ] = src ;
inq[ src ]++ ;
Q.push( src ) ;
while( !Q.empty() )
{
u = Q.front() ;
Q.pop() ;
inq[ u ]-- ;
temp = List[ u ] ;
while( temp != NULL )
{
int v= temp-> to ;
if( dist[ v ] > dist[ u ] + temp->weight )
{
dist[ v ] = dist[ u ] + temp -> weight ;
path[ v ] = u ;
if( !inq[ v ] )
{
Q.push( v ) ;
inq[ v ]++ ;
}
}
temp = temp -> next ;
}
}
}

int main()
{
int i , j ;
int u , v , w ;
scanf( "%d" , &n );
memset( List , 0 , sizeof( List ) ) ;
ArcNode *temp ;
while( 1 )
{
scanf( "%d%d%d" ,&u , &v , &w ) ;
if( u == -1 && v == -1 && w == -1 )
break ;
temp = new ArcNode ;
temp -> to = v ;
temp -> weight = w;
temp -> next = NULL ;
if( List[ u ] == NULL )
List[ u ] = temp ;
else
{
temp -> next = List[ u ] ;
List[ u ] = temp ;
}
}
SPFA( 0 ) ;
for( j = 0 ; j < n ; j++ )
{
temp = List[ j ] ;
while( temp != NULL )
{
List[ j ] = temp -> next ;
delete temp ;
temp = List[ j ] ;
}
}
int shortest[ maxn ] ;
for( i = 1 ; i < n ; i++ )
{
printf( "%d " , dist[ i ] ) ;
memset( shortest , 0 , sizeof( shortest ) ) ;
int k = 0 ;
shortest[ k ] = i ;
while( path[ shortest[ k ] ] != 0 )
{
k++ ;
shortest[ k ] = path[ shortest[ k - 1 ] ] ;
}
k++ ;
shortest[ k ] = 0 ;
for( j = k ; j > 0 ; j-- )
printf( "%d->" , shortest[ j ] ) ;
printf( "%d
" , shortest[ 0 ] ) ;
}
}

/*

7
0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3
-1 -1 -1
1 ? ? ? 0->3->2->1
3 ? ? ? 0->3->2
5 ? ? ? 0->3
0 ? ? ? 0->3->2->1->4
4 ? ? ? 0->3->5
3 ? ? ? 0->3->2->1->4->6

*/

相关文档

  • 优秀教师发言稿范文
  • 街道党工委三问三解活动总结
  • 原来还是要扣掉一分
  • 孤独的孩子、要好好珍惜快乐
  • 2020年山西运城市中心医院招聘聘用制人员公告(36人)
  • n皇后问题(dfs+剪枝)
  • 《定风波》
  • 虾蛄怎么养
  • 民意调查:奥巴马竟成10年来最受尊敬的人?
  • 面试必问,单例模式
  • 写一句勉励人勤奋学习的名言
  • 科目二S弯道及曲线行驶技巧
  • 猪毛菜的功效与作用
  • 西餐红酒牛排的做法
  • 陆羽煎茶
  • 中医治疗心力衰竭偏方有哪些
  • 2021年幼儿园班级六一儿童节活动总结
  • 英魂之刃对敌小知识
  • 常见的六种牛奶有哪些?牛奶的致命喝法
  • 皮皮虾怎么关闭点赞通知提醒?
  • WebCollector内核解析?如何设计一个爬虫
  • xp系统密钥
  • 道教有哪些禁忌
  • 擅自设立保险公司要承担什么法律责任
  • babycare故事机怎么样babycare早教机使用测评
  • 2021领导个人学习计划
  • 学生卫生部长竞选稿
  • 女生夏天穿什么鞋子情迷精致单鞋
  • 简单数学易错题手抄报资料以及图片
  • 壁挂炉出现of是什么意思
  • 猜你喜欢

  • 最新冀教版六年级上册《将军与孤女》PPT课件(2016)]优质公开课精品优质公开课精品
  • 2019年十年后回看童年小学作文500字-精选word文档 (1页)
  • 从五个方面入手做一名新时代的好干部
  • 抵押担保借款合同
  • 20XX年整治违法排污企业保障群众健康环保专项行动工作方案
  • 上犹县熳筠服饰有限公司企业信用报告-天眼查
  • 要想统计数据用什么办公软件好啊
  • 推荐-防治水安全评价制度
  • 【优质】最新语文冀教版小学五年级下册《狼牙山五壮士》公开课教案
  • 银行日记账的日结
  • 2018-2019年长春市朝阳实验小学校三年级上册科学模拟复*题无答案
  • 融合汇(唐山)食品有限公司(企业信用报告)- 天眼查
  • 深圳市耀陆实业有限公司郴州分公司企业信用报告-天眼查
  • 2020苏科初中数学七年级上册《2.4 绝对值与相反数》PPT课件 (1).ppt
  • 备战2020年高考政治一轮精品复*第五课把握思维的奥妙教案(1)
  • 北京兴农先丰教育科技有限公司企业信用报告-天眼查
  • transform: translateY(-50%) 绝对定位 实现图片垂直居中效果
  • 新外研版小学英语四年级下册Review module Unit 1 教案.doc(精品).doc
  • 体育部2020年上学期工作总结
  • 机械加工实训材料PVC塑料制品研究
  • 新年
  • 七年级历史上册_第14课_匈奴的兴起与汉朝的和战课件_(新版)新人教版
  • 基于Android的林业科技英语词汇查询系统设计
  • 2020年小学语文教研组下学期的工作计划
  • 猪蹄真的能美容吗?
  • 七年级语文下册《从百草园到三味书屋》*题集人教版
  • 第17课 综合探究:探索中国*代政体变化的艰难历程教学课件设计(1)
  • 何克抗教授:关于中国特色教育技术的自主创新-文档资料
  • 工作表 在 159 工管部-转发中国中铁关于切实做好工程施工技术管理六项制度建设和执行工作的通知20140604
  • 2018艺术硕士报考条件跨专业
  • 八年级语文下册组歌知识点
  • 河南省虞城县第一初级中学八年级地理上册第2节 工业导学案
  • 上海江南第一家食苑企业信用报告-天眼查
  • 江?小学第一学期开学典礼大队辅导员讲话稿
  • 软土深基坑工程咬合桩围护结构施工应用问题分析
  • 四年级暑假日记300字_CHEER华丽的冒险
  • 韶关市人民政府关于表彰2002年度全市外经贸和内联引资工作先进集体的通报
  • 工信部“节能产品惠民工程”节能汽车推广实施细则印发
  • 2012届高三物理一轮复*精品资料:磁场(高考真题+模拟新题)(有详解)
  • 2018_2019学年高中历史第3单元第9课资本主义政治制度在欧洲大陆的扩展*题新人教版必修1
  • 九年级英语全册 Unit 4 I used to be afraid of the d
  • 2017年秋九年级历史上册第1单元世界古代史检测卷同步*题岳麓版
  • 电脑版