Bellman-Ford算法
#include<iostream>
using namespace std;
const int V=101;
const int E=101;
#define typec int // type of cost
const typec inf=0x3f3f3f3f; // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c)
{
if (dist[v] > dist[u] + c)
{
dist[v] = dist[u] + c;
pre[v] = u;
return 1;
}
return 0;
}
int bellman (int src)
{
int i, j;
for (i=0; i<n; ++i)
{
dist[i] = inf;
pre[i] = -1;
}
dist[src] = 0;
bool flag;
for (i=1; i<n; ++i)
{
flag = false;
for (j=0; j<m; ++j)
{
if( 1 == relax(edge[j][0], edge[j][1],
edge[j][2]) ) flag = true;
}
if( !flag ) break;
}
for (j=0; j<m; ++j)
{
if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
return 0
}
return 1;
}
int main()
{
int i;
int src;
cin>>n>>m;
for(i=0; i<m; ++i)
{
cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
}
cin>>src;
cout<<bellman(src)<<"\n";
for(i=0; i<n; i++)
{
cout<<dist[i]<<' ';
}
cout<<'\n';
return 0;
}
模版的使用，Bellman-Ford算法，复杂度O(VE)，可解决负权边，判别负权回路。
额外采用Yen氏改进，但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。
2019年6月13日 20:09
This is really a splendid blog that shares the unique and informative stuff of writings and articles with us that help us a lot in enhancing our knowledge but you can meet with ninjaessays.com writers for unique task. I like to visit this blog on a daily basis and also to share it with my friends.
2019年8月22日 15:36
Hi guys! Thank you for sharing valuable information. Click on this website link to read the really good educational affordable paper and <a href="https://exclusive-paper.com/college-term-paper.php">buy college term paper</a>! If you need substantial help and firm support with your assignments, access our service and fill in the order form.
2019年8月22日 15:37
Are you spending sleepless nights trying to work on your writing assignment? Are you worried that you may not be able to meet your college term paper deadline? Do you need professional assistance in order to get excellent marks in your custom essays? Visit https://exclusive-paper.com/college-term-paper.php
2019年11月19日 05:36
Your blog is incredibly interesting! Thank you for such fruitful work. I love to analyze new information successfully in the future to use it. I do not waste my precious work on precious time and trusting to https://super-essays-service.com/
2022年9月27日 20:48
Subject experts of Kendriya Vidyalaya Sangathan have designed the Elementary level Pre School education subject-wise sample paper for practice as mock tests through KVS 1st Class Model Paper 2023 for all regional students of Hindi medium, KVS 1st Class Question Paper English medium, and other regional languages students to the academic year of 2023. Subject experts of Kendriya Vidyalaya Sangathan have designed the Elementary level Pre School education subject-wise sample paper for practice as mock tests through KVS 1st Class Model Paper 2023 for all regional students of Hindi medium.
2023年7月29日 21:52
Dependiendo de su configuración de seguridad, es posible que también deba verificar su identidad a través de la autenticación de dos factores u otros medios. Una vez que su cuenta esté activada, puede personalizar su perfil, https //www.microsoft.com/link xbox conectarse con otros jugadores y comenzar a explorar las numerosas funciones de Xbox. También puede comprar una membresía de Xbox Live Gold para acceder a más funciones, incluidos juegos gratuitos, descuentos exclusivos y juegos en línea con otros jugadores de todo el mundo.
2023年8月01日 18:47
SCERT Sikkim Follows NCERT Curriculum These Textbooks are Updated as per the Syllabus Prescribed by SCERT Sikkim. Students of 4th Class Should follow Prescribed Textbooks while Preparing for Exam.Our Sikkim 4th Class Textbook 2024 Team Refer to the Respective Subject Textbook while Preparing the Final Important questions. Students Best Practice Study Materiel about Textbooks are the Fact that they are so Comprehensible that it does not require the aid of a Subject Literate.SCERT Sikkim once Publishes the Sikkim Elementary School Textbooks 2024 Other Study materials on the official web site, we will update the Information on this page.
2023年12月11日 01:06
백링크하이's commitment to quality is unmatched. They're a game-changer in the SEO industry.
2023年12月12日 19:25 I loved the local experience 제주오피 provided. Staying here allowed me to soak in the charm of Jeju.
2023年12月16日 13:00
Thank you for the article. I’ve truly thought about it before but never wanted to do anything about it. I do think because of my lack of complete understanding. Each day, however, I’m noticing more and more people getting frustrated because they think it is very complicated to understand. Exactly what really encouraged me personally again, however, seemed to be your rationale men and women would like to discuss the situation once they see their own friends commenting on the same thing. That is just how knowledge increases. NBA중계
2023年12月16日 19:25
I've recommended 누누티비 to all my friends, and they're hooked too.
2023年12月16日 20:10
I love the flexibility of scheduling 러시아마사지. It fits perfectly into my busy lifestyle.
2023年12月20日 14:58
I can't recommend 대구오피 enough. The attention to detail and commitment to customer satisfaction make it stand out.
2023年12月23日 15:44
With 설문조사 사이트 무료, you can seamlessly integrate surveys into your events, lectures, and promotions.
2023年12月26日 22:12
Hello! I just want to give a huge thumbs up for the great info you have here on this blog. I will be coming back aimed at your website for additional soon. 카지노사이트
2023年12月27日 21:43
I've become the go-to source for무료스포츠중계recommendations among my friends. It's too good to keep to myself.
2024年1月03日 17:01
안전카지노 is the best online casino, hands down!
2024年1月06日 17:01
JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who are passionate about providing engaging content that is accurate, interesting, and worthy to read. We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on each topic possible with the help of the editorial and content team.
2024年1月06日 19:28
천안오피's ambiance is soothing. Their Swedish Massage is a treat for body and mind.
2024年1月11日 19:44
인천출장마사지's serene ambiance and skilled therapists make it a must-visit in Incheon.