每对顶点间的最短距离 稀疏有向图Johnson算法 C++实现
// 稀疏有向图Johnson算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define Infinity 65535
#define MAX 100
using namespace std;
//边尾节点结构体
struct edgeNode
{
int no;//节点序号
int weight; //此边权值
edgeNode *next; //下一条邻接边
};
//节点信息
struct vexNode
{
char info; //节点序号
edgeNode *link; //与此节点为首节点的边的尾节点链表
};
//优先队列元素结构体
struct PriQue
{
int no; //节点元素序号
int weight; //源点到此节点的权值
};
//节点数组
vexNode adjlist[MAX];
//添加一个序号为0节点到其他各节点的最小权值
int d[MAX];
//源点到各节点的最小权值
int lowcost[MAX];
//各节点对间的最小权值
int mincost[MAX][MAX];
//优先队列
PriQue queue[2*MAX];
//建立图的邻接表
void createGraph(vexNode *adjlist,int n,int e)
{
int i;
cout<<"请输入这些节点的信息："<<endl;
for(i=1;i<=n;i++)
{
cout<<"节点"<<i<<"的名称:";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
}
cout<<"请输入这些边的信息："<<endl;
int v1,v2;
edgeNode *p1;
int weight1;
for(i=1;i<=e;i++)
{
cout<<"边"<<i<<"的首尾节点：";
cin>>v1>>v2;
cout<<"请输入此边的权值：";
cin>>weight1;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v2;
p1->weight = weight1;
p1->next = adjlist[v1].link;
adjlist[v1].link = p1;
}
//添加节点0，到每一个节点的距离都是0
adjlist[0].info ='0';
adjlist[0].link = NULL;
for(i=n;i>=1;i--)
{
d[i] = 0;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = i;
p1->weight = 0;
p1->next = adjlist[0].link;
adjlist[0].link = p1;
}
}
//bellman_ford算法求节点0到其他各节点的最短距离
bool bellman_ford(vexNode *adjlist,int *d,int n)
{
int i,j;
d[0] = 0;
edgeNode *p1;
for(j=1;j<=n;j++)
{
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
if(d[p1->no]>d[i]+p1->weight)
d[p1->no] = d[i] + p1->weight;
p1 = p1->next;
}
}
}
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
if(d[p1->no]>d[i]+p1->weight)
return false;
p1 = p1->next;
}
}
return true;
}
//johnson算法中，需要对每一条边重新赋权值产生非负的权
void G_w_to_G1_w1(int *d,const int n)
{
int i;
edgeNode *p1;
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
p1->weight = p1->weight + d[i] - d[p1->no];
p1 = p1->next;
}
}
}
//保持优先队列的优先性，以指定源点到每一点的最少距离为关键字
void keep_heap(PriQue *queue,int &num,int i)
{
int smallest = i;
int left = 2*i,right = 2*i+1;
if(left<=num&&queue[left].weight<queue[i].weight)
smallest = left;
if(right<=num&&queue[right].weight<queue[smallest].weight)
smallest = right;
if(smallest != i)
{
PriQue q = queue[smallest];
queue[smallest] = queue[i];
queue[i] = q;
keep_heap(queue,num,smallest);
}
}
//插入一个元素到优先队列中，并保持队列优先性
void insert_heap(PriQue *queue,int &num,int no,int wei)
{
num += 1;
queue[num].no = no;
queue[num].weight = wei;
int i = num;
while(i>1&&queue[i].weight<queue[i/2].weight)
{
PriQue q1;
q1 = queue[i/2];
queue[i/2] = queue[i];
queue[i] = q1;
i = i/2;
}
}
//取出队列首元素
PriQue heap_extract_min(PriQue *queue,int &num)
{
if(num<1)
return queue[0];
PriQue que = queue[1];
queue[1] = queue[num];
num = num -1;
keep_heap(queue,num,1);
return que;
}
//dijkstra算法求节点i到其他每一个节点的最短距离
void dijkstra(vexNode *adjlist,PriQue * queue,int i,const int n,int &num)
{
int v = i;
//lowcost[v] = 0;
int j;
for(j=1;j<n;j++)
{
edgeNode *p1 = adjlist[v].link;
while(p1 != NULL)
{
if(lowcost[p1->no] > lowcost[v] + p1->weight)
{
lowcost[p1->no] = lowcost[v] + p1->weight;
insert_heap(queue,num,p1->no,lowcost[p1->no]);
}
p1 = p1->next;
}
v = heap_extract_min(queue,num).no;
if(v==0)
{
cout<<"队列中没有节点！"<<endl;
return;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数：";
cin>>cases;
//用队列0元素作为哨兵，如果队列中没有元素，则返回队列0元素
queue[0].no = 0;
queue[0].weight = 0;
while(cases--)
{
int n,e;
cout<<"请输入节点数：";
cin>>n;
cout<<"请输入边数：";
cin>>e;
//队列中的元素，初始为0
int num = 0;
int i,j;
//创建邻接表
createGraph(adjlist,n,e);
cout<<endl;
memset(d,Infinity,sizeof(d));
//bellman_ford算法求节点0到其他各节点的最短距离
bool flag = bellman_ford(adjlist,d,n);
if(!flag)
{
cout<<"此图存在负回路，不正确！"<<endl;
continue;
}
//johnson算法中，需要对每一条边重新赋权值产生非负的权
G_w_to_G1_w1(d,n);
//运用dijkstra算法求得每一对节点间的最短距离
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
lowcost[j] = Infinity;
lowcost[i] =0;
dijkstra(adjlist,queue,i,n,num);
//重新把原值赋值回来，因为在函数G_w_to_G1_w1()中改变过
for(j=1;j<=n;j++)
mincost[i][j] = lowcost[j] + d[j] - d[i];
}
cout<<"下面输出每一对顶点之间的最短距离："<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"顶点("<<i<<":"<<adjlist[i].info<<")到顶点("<<j<<":"<<adjlist[j].info<<")的最短距离为："<<mincost[i][j]<<endl;
}
}
system("pause");
return 0;
}
-------------------------------------------程序测试----------------------------------------------------------
请输入案例的个数：1
请输入节点数：5
请输入边数：9
请输入这些节点的信息：
节点1的名称:a
节点2的名称:b
节点3的名称:c
节点4的名称:d
节点5的名称:e
请输入这些边的信息：
边1的首尾节点：1 2
请输入此边的权值：3
边2的首尾节点：1 3
请输入此边的权值：8
边3的首尾节点：1 5
请输入此边的权值：-4
边4的首尾节点：2 4
请输入此边的权值：1
边5的首尾节点：2 5
请输入此边的权值：7
边6的首尾节点：3 2
请输入此边的权值：4
边7的首尾节点：4 1
请输入此边的权值：2
边8的首尾节点：4 3
请输入此边的权值：-5
边9的首尾节点：5 4
请输入此边的权值：6
下面输出每一对顶点之间的最短距离：
顶点(1:a)到顶点(1:a)的最短距离为：0
顶点(1:a)到顶点(2:b)的最短距离为：1
顶点(1:a)到顶点(3:c)的最短距离为：-3
顶点(1:a)到顶点(4:d)的最短距离为：2
顶点(1:a)到顶点(5:e)的最短距离为：-4
顶点(2:b)到顶点(1:a)的最短距离为：3
顶点(2:b)到顶点(2:b)的最短距离为：0
顶点(2:b)到顶点(3:c)的最短距离为：-4
顶点(2:b)到顶点(4:d)的最短距离为：1
顶点(2:b)到顶点(5:e)的最短距离为：-1
顶点(3:c)到顶点(1:a)的最短距离为：7
顶点(3:c)到顶点(2:b)的最短距离为：4
顶点(3:c)到顶点(3:c)的最短距离为：0
顶点(3:c)到顶点(4:d)的最短距离为：5
顶点(3:c)到顶点(5:e)的最短距离为：3
顶点(4:d)到顶点(1:a)的最短距离为：2
顶点(4:d)到顶点(2:b)的最短距离为：-1
顶点(4:d)到顶点(3:c)的最短距离为：-5
顶点(4:d)到顶点(4:d)的最短距离为：0
顶点(4:d)到顶点(5:e)的最短距离为：-2
顶点(5:e)到顶点(1:a)的最短距离为：8
顶点(5:e)到顶点(2:b)的最短距离为：5
顶点(5:e)到顶点(3:c)的最短距离为：1
顶点(5:e)到顶点(4:d)的最短距离为：6
顶点(5:e)到顶点(5:e)的最短距离为：0
请按任意键继续. . .
分享到：
相关推荐
在本项目中，开发者在Visual Studio 2008（VS2008）环境下使用C++语言实现了Dijkstra算法，以解决有向图中的最短路径问题。 首先，我们需要理解Dijkstra算法的基本原理。它通过贪心策略，每次选取当前未访问节点中...
在本文中，我们将设计一个算法来求图中一个源点到其他各顶点的最短路径。...本文设计了一种基于邻接表的算法来求图中一个源点到其他各顶点的最短路径，并使用Dijkstra算法和冒泡排序法来实现该算法。
Floyd算法，全称为Floyd-Warshall算法，是一种用于解决图论问题的著名算法，主要用来寻找有向图或无向图中所有顶点之间的最短路径。它由美国计算机科学家Robert W. Floyd在1962年提出，因此得名。这个算法的核心思想...
本文将详细讲解如何使用C#语言实现有向图算法，包括邻接表、关键路径、深度优先搜索（DFS）和广度优先搜索（BFS），以及拓扑排序。 首先，我们要理解有向图的概念。有向图是由顶点（节点）和边组成的，边具有方向性...
### 图的邻接表C++表示 在计算机科学领域，图是一种重要的数据结构，用于模拟对象之间的关系。根据图中的边是否具有方向性，可以将图分为无向图和有向图。对于稀疏图（即边的数量远小于顶点数量的平方），邻接表是...
数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)
总结来说，解决C++中最短路径问题的关键在于理解图的表示方法，选择合适的算法，以及有效地实现这些算法。Dijkstra和Floyd-Warshall是两种常用的解决方案，各有优缺点，适用于不同的场景。在实际编程中，你还需要...
有向图邻接矩阵c++运算操作 基本操作 邻接矩阵 c++实现
在图的邻接表中，每个顶点都有一个列表，存储了与该顶点相连的所有边的目标顶点。这种方式节省了空间，因为对于稀疏图（边的数量远小于顶点数量的平方）来说，邻接表比邻接矩阵更加紧凑。 Dijkstra算法是求解图中...
这段代码首先创建一个无向图，然后从顶点0开始运行Dijkstra算法，打印出从顶点0到其他所有顶点的最短距离。请注意，这里的边权重被假设为1，如果有不同的权重，需要在`addEdge`方法中进行调整并在Dijkstra算法中相应...
### 基于Java多线程实现所有顶点间最短路径的并行算法 #### 概述 本文探讨了一种使用Java多线程技术来实现所有顶点间最短路径问题的并行算法。该算法主要针对的是图论中的经典问题——最短路径问题，并通过对...
### 单源最短路径问题解析 ...该算法适用于带权有向图，并且能够高效地找到从源点到图中每个顶点的最短路径。此外，通过适当的优化和扩展，还可以应用于更广泛的场景中，如动态规划问题、网络路由选择等。
迪杰斯特拉（Dijkstra）算法是一种用于寻找有向图中单源最短路径的经典算法，由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。在这个算法中，我们从一个源节点开始，逐步扩展最短路径到其他节点，直到到达所有...
- **时间复杂度**：采用邻接表实现的Prim算法，其时间复杂度为O(ElogV)，其中E是边的数量，V是顶点的数量。这是因为每次从候选边中选择权重最小的边都需要进行排序或查找操作。 - **空间复杂度**：主要取决于邻接表...
c++求图的最短路径算法 最短路径算法是图论中一个重要的概念，它是指在图中找出从一个顶点到另一个顶点的最短路径。该算法有很多种实现方法，如Dijkstra算法、Floyd算法、Bellman-Ford算法等。 在本实验中，我们...
Dijkstra算法是一种解决有向图中单源最短路径问题的高效算法，前提条件是图中所有边的权重必须是非负的。该算法的核心思想是使用贪心策略，逐步扩展从源点出发的最短路径。算法维护了一个集合S，包含了已找到最短...
对于稀疏图（边的数量远小于顶点数量的平方），Dijkstra算法或Bellman-Ford算法可能更为高效，因为它们只处理有边的顶点对。 ### 5. 文件解析 在提供的压缩包中，"Floyd求最短路径"可能是实现Floyd算法的C++源代码...
该算法主要用于寻找带权重的有向或无向图中，从一个特定顶点到其他所有顶点的最短路径。Dijkstra算法的核心思想是贪心策略，它每次选择当前未访问顶点中距离起点最近的一个，并更新与它相邻的顶点的距离。 源代码...
它适用于有向图和无向图，但要求图中的所有边权重均为非负值。该算法通过逐步扩展一个顶点集合S，使得S内的所有顶点到起始顶点的距离均已被确定。 #### 程序分析 本程序实现了基于邻接矩阵表示的Dijkstra算法，并用...
首先，邻接表是图数据结构的一种高效存储方式，尤其适用于稀疏图（边的数量远小于顶点数量的平方）。它为每个顶点维护一个列表，列出与该顶点相连的所有边。相比于邻接矩阵，邻接表可以节省大量空间，且在遍历边时...