本篇文章给大家谈谈johnson算法c语言,以及johnson语言学家对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
1、用Jonhnson-Trotter算法实现全排列2、C语言打印图中两点之间的所有路径,不是最短路径!!!谢谢高手麻烦帮忙 代码要实现哈!3、johnson算法是什么?
用Jonhnson-Trotter算法实现全排列
在此只需实现1到n这n个整数的全排列即可。
以下是源码:
struct node{
int num;
bool flag;
};
void JohnsonTrotter(int n)
{
node* a = new node[n + 1];
int i;
for (i = 0; i = n; i++)
{
a[i].num = i;
a[i].flag = false;
}
int k = 1;
node tp;
C语言打印图中两点之间的所有路径,不是最短路径!!!谢谢高手麻烦帮忙 代码要实现哈!
这是我写的程序和运行的结果,如果有不会的地方依然可以问我。
/*
首先我想说明几点问题。
1.我不知道你的题意中的路径是单向的还是双向的,不过我把路径设置成双向的了
2.说一下我程序的输入,首先输入一个n,表示该图中有n条路;然后有n行,每行
两个数x, y(1=x, y=99),表示这两个地点有一条路径。最后输入两个数,
表示计算这两点之间所有的路径
3.我的思路用的是深搜,不过广搜也是可以的
*/
#include stdio.h
#include math.h
int path[100][100];///path[i][j]为0表示i, j两点之间不通,为1表示有一条路
int stack[120], m=1, n, x, y;///存储路径
void dfs(int p)
{
int i, j;
for(i=1; i=100; i++)
{
if(path[p][i]==1)
{
if(i == y)///如果深搜到了终点,就输出刚才经过的路径
{
for(j=0; jm; j++)
{
printf(“%-5d”, stack[j]);
}
printf(“%-5d\n”, y);
}
else///如果该点不是终点
{
stack[m] = i;///将该点存起来
m++;
dfs(i);///接着深搜
m–;
}
}
}
}
int main()
{
int i, j;
memset(path, 0, sizeof(path));
scanf(“%d”, n);
for(i=0; in; i++)
{
scanf(“%d %d”, x, y);
path[x][y] = path[x][y] = 1;///这两点之间有路径
}
scanf(“%d %d”, x, y);
stack[0] = x;
dfs(x);
}
johnson算法是什么?
Johnson算法适用于求All
Pairs
Shortest
Path.
Johnson算法应用了重标号技术,先进行一次Bellman-Ford算法,然后对原图进行重标号,w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra,每次Dijkstra的复杂度为O(nlogn+m),于是算法复杂度为O(n^2logn+m)。
关于求解流水作业调度问题的
Johnson
算法具体描述:
关于johnson算法c语言和johnson语言学家的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。