`
datoplay
  • 浏览: 1605733 次
文章分类
社区版块
存档分类
最新评论

单源最短路径Bellman_Ford算法C++实现

 
阅读更多

// 单源最短路径Bellman_Ford算法.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#define MAX 100
#define Infinity 65535
typedef int WeiType;
using namespace std;

struct edgeNode
{
int no; //边尾端的序号
char info; //边端的名称
WeiType weight; //边权值
struct edgeNode * next; //下一个
};

struct vexNode
{
char info; //节点名称
struct edgeNode *link; //与之相连的端点
};

//存储节点信息
vexNode adjlist[MAX];
//前驱节点
int parent[MAX];
//源点到节点j最短路径的花费
WeiType lowcost[MAX];

//建立邻接表存储
//adjlist为节点集,n为节点个数,e为边数目
//返回源点序号
int createGraph(vexNode *adjlist,int n,int e)
{
int i;
for(i=1;i<=n;i++)
{
cout<<"请输入节点"<<i<<"的名称:";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
parent[i] = i;
lowcost[i] = Infinity;
}
edgeNode *p1;
int v1,v2;
WeiType weight;
for(i=1;i<=e;i++)
{
cout<<"请输入边"<<i<<"的起始节点与尾节点序号:";
cin>>v1>>v2;
cout<<"请输入此边的权值:";
cin>>weight;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v2;
p1->weight = weight;
p1->info = adjlist[v2].info;
p1->next = adjlist[v1].link;
adjlist[v1].link = p1;
}
cout<<"请输入源点序号:";
int v0;
cin>>v0;
lowcost[v0] = 0;
return v0;
}

/*
//
void relax(WeiType *lowcost,int *parent,const int u,const int v,const WeiType w)
{
if(lowcost[v]>lowcost[u]+w)
{
lowcost[v] = lowcost[u] + w;
parent[v] = u;
}
}
*/
//
bool Bellman_Ford(vexNode *adjlist,WeiType *lowcost,int *parent,const int n)
{
int i,j;
for(j=1;j<n;j++)
{
for(i=1;i<=n;i++)
{
edgeNode *p1 = adjlist[i].link;
while(p1 != NULL)
{
if(lowcost[i]+p1->weight <lowcost[p1->no])
{
lowcost[p1->no] = lowcost[i]+p1->weight;
parent[p1->no] = i;
}
p1 = p1->next;
}
}
}
//检查有无负回路
for(i=1;i<=n;i++)
{
edgeNode *p2 = adjlist[i].link;
while(p2 != NULL)
{
if(lowcost[p2->no]>lowcost[i]+p2->weight)
return false;
p2 = p2->next;
}
}
return true;
}

//打印源点到节点i最短路径
void print_it(vexNode *adjlist,int *parent,const int v0,const int i)
{
if(i == v0)
cout<<"("<<v0<<":"<<adjlist[v0].info<<") ";
else
{
print_it(adjlist,parent,v0,parent[i]);
cout<<"("<<i<<":"<<adjlist[i].info<<") ";
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
int n,e;
cout<<"请输入节点数:";
cin>>n;
cout<<"请输入边数:";
cin>>e;
//创建邻接表
int v0 = createGraph(adjlist,n,e);
//调用Bellman-Ford算法
bool flag = Bellman_Ford(adjlist,lowcost,parent,n);
int i;
//输出源点到其余每一点的最短路径(节点序号:节点名称)
for(i=1;i<=n;i++)
{
cout<<"从源点"<<adjlist[v0].info<<"到点"<<adjlist[i].info<<"的路径为:"<<endl;
print_it(adjlist,parent,v0,i);
cout<<endl;
cout<<"此路径花费为:"<<lowcost[i]<<endl;

}
}
system("pause");
return 0;
}

--------------------------------------------------------程序测试--------------------------------------------------------

请输入案例的个数:1
请输入节点数:5
请输入边数:10
请输入节点1的名称:s
请输入节点2的名称:t
请输入节点3的名称:x
请输入节点4的名称:y
请输入节点5的名称:z
请输入边1的起始节点与尾节点序号:1 2
请输入此边的权值:6
请输入边2的起始节点与尾节点序号:1 4
请输入此边的权值:7
请输入边3的起始节点与尾节点序号:2 3
请输入此边的权值:5
请输入边4的起始节点与尾节点序号:2 4
请输入此边的权值:8
请输入边5的起始节点与尾节点序号:2 5
请输入此边的权值:-4
请输入边6的起始节点与尾节点序号:3 2
请输入此边的权值:-2
请输入边7的起始节点与尾节点序号:4 3
请输入此边的权值:-3
请输入边8的起始节点与尾节点序号:4 5
请输入此边的权值:9
请输入边9的起始节点与尾节点序号:5 1
请输入此边的权值:2
请输入边10的起始节点与尾节点序号:5 3
请输入此边的权值:7
请输入源点序号:1
从源点s到点s的路径为:
(1:s)
此路径花费为:0
从源点s到点t的路径为:
(1:s) (4:y) (3:x) (2:t)
此路径花费为:2
从源点s到点x的路径为:
(1:s) (4:y) (3:x)
此路径花费为:4
从源点s到点y的路径为:
(1:s) (4:y)
此路径花费为:7
从源点s到点z的路径为:
(1:s) (4:y) (3:x) (2:t) (5:z)
此路径花费为:-2
请按任意键继续. . .

分享到:
评论

相关推荐

    aa.zip_C++ 图论的库_bellman_starfish_单源最短路径_图论最小路径

    图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法 语言 C++ 编译平台 ...

    图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bell

    图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法

    图论算法库 C++ 语言实现.zip_C++图论_C++图论的库_c++ 图论库_starfish_图论最优路径

    单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法 语言 C++ 编译平台 VisualAge C++ 4.0 作者 starfish (starfish.h@china.com) 备注 程序用C++语言编写,在Visual...

    C++计算任意权值的单源最短路径(Bellman-Ford)

    一、有Dijkstra算法求最短路径了,为什么还要用Bellman-Ford算法 Dijkstra算法不适合用于带有负权值的有向图。 如下图: 用Dijkstra算法求顶点0到各个顶点的最短路径: (1)首先,把顶点0添加到已访问顶点集合S中,...

    单源最短路径Leetcode-AlgImpl:http://myencyclopedia.top/blog上描述的算法

    单源驱动路径Leetcode 算法实现 算法在我的博客中有描述 01_Mining_of_Massive_Datasets ...单源最短路径(负权重) 03 Floyd-Warshall All Pairs 最短路径 04_MaxFlow_and_Bipartite 01 双向测试 02 双边比赛匈牙利语

    图算法(c++模板)

    用c++模板写的图算法,包括广搜、深搜、最小生成树算法(prim、kruskal)、单源最短路径(bellman-ford、dijkstra)、拓扑排序,prim、dijkstra算法使用优先级队列实现

    SPFA带负权的最短路径算法

    SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。

    队列优化的Bellmanford最短路算法(SPFA)C++实现

    使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一个点,这个点到最远点的长度最短。图使用邻接表保存。

    csci-163b

    CSCI 163B / 164-算法高级理论 这是我对CSCI 163B / 164中不同图形算法的C ++实现-Nicholas Tran教授的高级算法理论。...Bellman-Ford单源最短路径算法负体重循环 Dijkstra单源最短路径算法Dary堆实现 Floyd-

    C C++算法实例.c

    9.判断图中是否有负权回路 Bellman-ford 算法 10.第n最短路径问题 三、背包问题 1.0-1背包: 每个背包只能使用一次或有限次(可转化为一次): 2.可重复背包 四、排序算法 A.快速排序: B.插入排序: C....

    全面的算法代码库

    单源最短路径(Bellman-Ford) Bellman-Ford 使用Edmonds-Karp进行二分图匹配 Bigrpah-Matching(Edmonds-Karp) 普通的二叉搜索树 Binary-Search-Tree 广度优先搜索 Breadth-First-Search 冒泡排序 Bubble-Sort ...

    算法导论(part2)

    ·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...

    算法导论(part1)

    ·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...

    C++队列优化的Bellmanford最短路算法(SPFA)

    摘要:VC/C++源码,算法相关,队列优化,最短路径算法 C++队列优化的Bellmanford最短路算法(SPFA),使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一...

    suanfa.rar_SPFA

    C++队列优化的Bellmanford最短路算法(SPFA),使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一个点,这个点到最远点的长度最短。图使用邻接表保存...

Global site tag (gtag.js) - Google Analytics