数据结构 C++ 迪杰斯特拉算法最短路径求补充完整。分还可以再加
Dijkstra 迪杰斯特拉算法 数据结构
//求单源点最短路径
#include "stdafx.h"
#include
const int n=5; //图中定点个数
const int e=9; //图中边的个数
#define max 32767
class Graph
{
public:
int arcs[n+1][n+1]; //图的邻接矩阵
int dist[n+1]; //存放源点到个顶点的最短路径
int path[n+1]; //存放在最短路径上该顶点的前一顶点号
int s[n+1]; //已求得的在最短路径上的顶点的顶点号
void shortest_path(Graph &t, const int V1);
};
void Graph::shortest_path(Graph &t, const int V1)
{
for(int i=1; i<=n; i++)
{t.dist[i]=t.arcs[V1][i];
t.s[i]=0;
if((i!=V1)&&(t.dist[i]<max))t.path[i]=V1;
else t.path[i]=0;
}
t.s[V1]=1; t.dist[V1]=0;
for(i=1; i<n; i++)
{
int min=max; int u=V1;
for(int j=1; j<=n; j++)
if(!t.s[j]&&t.dist[j]<min){u=j,min=t.dist[j];}
t.s[u]=1;
for(int w=1; w<=n;w++)
if(!t.s[w]&&t.arcs[u][w]<max&&t.dist[u]+t.arcs[u][w]<t.dist[w]){t.dist[w]=t.dist[u]+t.arcs[u][w]; t.path[w]=u;}
}
for(i=1; i<=n; i++)
{
if(i!=V1)
{
cout<<t.dist[i]<<":";
cout<<i;
int pre=t.path[i];
while(pre!=0)
{ cout<<"←"<<pre;
pre=t.path[pre];
}
cout<<endl;
}
}
}
int main(int argc, char* argv[])
{
Graph t;
int i,j,w;
for( i=1; i<=n;i++)
for(j=1; j<=n; j++)
if(i==j)t.arcs[i][j]=0;
else t.arcs[i][j]=max;
for(int k=1; k<=e; k++)
{
cin>>i>>j>>w;
t.arcs[i][j]=w;
}
t.shortest_path(t,1);
return 0;
}
哈夫曼树构造
#include "string.h"
#include "stdio.h"
#define MAXVALUE 1000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树叶结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 30 /*定义哈夫曼编码的最大长度*/
typedef struct
{ int bit[MAXBIT];
int start;
} HCODETYPE;
typedef struct
{ int weight;
int parent;
int lchild;
int rchild;
} HNODETYPE;
char *getcode1(char *s1,char *s2,char *s3) /*首先去掉电文中的空格*/
{ char temp[128]="",*p,*q;
p=s1;
while ((q=strstr(p,s2))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2); }
strcat(temp,p);
strcpy(s1,temp);
return s1;
}
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/
char * getcode (char *s1)
{ char s2[26],s5[26];
char temp[200]="",*p,*q,*r,*s3="";
int m,e,n=0;
m=strlen(s1);
while(m>0)
{ p=s1;
s2[0]=s1[0];
s2[1]='\0';
r=s2;
e=0;
while((q=strstr(p,r))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2);
e++; }
m-=e;
strcat(temp,p);
strcpy(s1,temp);
s5[n]=s2[0];
n++;
strcpy(temp,"");
}
s5[n]='\0';
strcpy(s1,s5);
printf(" 压缩后的电文（即叶结点）: %s
",s1);
return s1;
}
HNODETYPE huffmantree(char *s2,char s3[])
{ HNODETYPE huffnode[MAXNODE];
HCODETYPE huffcode[MAXLEAF],cd;
int sum,i,j,n1,n2,x1,x2,p,k,c;
char s1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','w','x','y','z'};
char s5[MAXLEAF];
int ww[26]={0},n=0;
strcpy( s5,s2);
sum=strlen(s2);
for(i=0;i<26;i++) /*统计所有字符出现的频度*/
for(j=0;j<sum;j++)
if(s2[j]==s1[i]) ww[i]++;
n=strlen(s3);
for (i=0;i<2*n-1;i++)
{ huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1; }
for(i=0;i<n;i++) /*分配给各叶结点权值*/
for(j=0;j<26;j++)
if (s3[i]==s1[j]) huffnode[i].weight=ww[j];
for (i=0;i<n-1;i++) /*构造哈夫曼树*/
{ n1=n2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{ if (huffnode[j].parent==-1 && huffnode[j].weight<n1)
{ n2=n1;
x2=x1;
n1=huffnode[j].weight;
x1=j; }
else
if (huffnode[j].parent==-1 && huffnode[j].weight<n2)
{ n2=huffnode[j].weight; x2=j;}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++) /*求每个叶结点的哈夫曼编码*/
{ cd.start=n-1;
c=i;
p=huffnode[c].parent;
while (p!=-1)
{ if (huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for (j=cd.start+1;j<n;j++)
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
printf(" 各叶结点对应哈夫曼编码 : ");/*输出每个叶结点的哈夫曼编码*/
for(i=0;i<n;i++)
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" ");}
printf("
电文的全部哈夫曼编码 : ");/*输出电文的全部哈夫曼编码*/
for(k=0;k<sum;k++)
for(i=0;i<n;i++)
if(s2[k]==s3[i])
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" "); }
printf("
");
}
main()
{
char s1[MAXLEAF],s2[MAXLEAF];
printf("
请输入电文 : ");
gets(s1);
strcpy(s2,getcode1(s1," ",""));
huffmantree(s1,getcode(s2));
}
求最小生成树的谱里姆算法
#include
using namespace std;
const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};
class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];
void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}
for(k=2;k<=n;k++)
{min=32767;
m=k-1;
for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};
void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;
for(int k=1;k<=e;k++)
{cout<<"输入一条边及边上的权值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}
t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
问题 1: 创建景点图的函数initgraph()里,因为邻接矩阵是对称矩阵,所以要对称赋值, 必须是用语句 c->arcs[j][i].adj=c->arcs[i][j].adj; 注意,是[j][i]在前, 而[i][j]在后. 而不是c->arcs[i][j].adj=c->arcs[j][i].adj;//错误问题 2: 函数allpath()能计算出最短路径的总线路长度,但是,显示的中途经过的顶点不对.代码的修改方案:对于"任意一点与其它各点的最短路径"的问题,可以用迪杰斯特拉(Dijkstra)算法,也可以用弗洛伊德(Floyd)算法,以下是修改后的代码,提供两个方案:void allpath_Floyd(mgraph c) //方案1:Floyd算法void allpath_Dijkstra(mgraph c) //方案2:Dijkstra算法如果有任何问题,可以百度私信给我.#include "stdio.h"#include "string.h"#define Infinity 9999#define MaxVertexNum 20typedef struct arcell //边的信息{ int adj; //权值}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];typedef struct vexsinfo //顶点信息{ int position; //景点的编号 char name[32]; //景点名 char introduction[56]; //景点的介绍}vexsinfo;typedef struct mgraph//使用邻接矩阵实现图的存储{ vexsinfo vexs[MaxVertexNum];//数组顶点向量,存顶点信息 adjmatrix arcs; //邻接矩阵 int vexnum,arcnum; //顶点数和边数}mgraph;mgraph c; //全局变量//创建景点图 (输入参数是指针)void initgraph(mgraph *c){ int i,j; c->vexnum=6; //顶点的总数量 c->arcnum=8; //边的总数量 for(i=0;ivexnum;i++)//设置顶点编号 { c->vexs[i].position=i; } strcpy(c->vexs[0].name,"v1"); strcpy(c->vexs[1].name,"v2"); strcpy(c->vexs[2].name,"v3"); strcpy(c->vexs[3].name,"v4"); strcpy(c->vexs[4].name,"v5"); strcpy(c->vexs[5].name,"v6"); //先初始化图的邻接矩阵 for(i=0;ivexnum;i++) { for(j=0;jvexnum;j++) { c->arcs[i][j].adj=Infinity; } }c->arcs[0][1].adj=7;c->arcs[0][2].adj=11;c->arcs[1][2].adj=10;c->arcs[1][3].adj=9;c->arcs[2][3].adj=5;c->arcs[2][4].adj=7;c->arcs[2][5].adj=8;c->arcs[4][5].adj=6;//邻接矩阵是对称矩阵,对称赋值 for(i=0;ivexnum;i++) { for(j=0;jvexnum;j++) { //注意,是[j][i]在前, 而[i][j]在后. c->arcs[j][i].adj=c->arcs[i][j].adj; } }}//查看景点间的路线 [需要改善]void allpath(mgraph c){ //求从顶点v0到其余顶点的最短路径p[]及带权长度d[v]（最短路径的距离） //p[][]数组用于存放两顶点间是否有通路标识，如果p[v][w]=1，则w是从v0到v的最短路径上的顶点 //visited[数组用于设置访问标志 int v,w,i,min,t=0,x; //变量t没有使用 int v0;//v0为起始景点的编号 int visited[20],d[20],p[20][20]; printf("
请输入一个起始景点的编号:"); scanf("%d",&v0); printf("
"); while(v0c.vexnum) { printf("
您输入的景点不存在
"); printf("请重新输入："); scanf("%d",&v0); } for(v=0;v%s",c.vexs[v].name); } printf("---->%s",c.vexs[v].name); printf("
总路线长为%d米:
",d[v]); }}//输出任意一点与其它各点的最短路径//算法: 弗洛伊德(Floyd)void allpath_Floyd(mgraph c){ int v,w,k; int v0; //输入的起始顶点编号 int P[MaxVertexNum][MaxVertexNum]; //二维数组P用于记录两点之间的路径下标 int D[MaxVertexNum][MaxVertexNum]; //二维数组D用于记录每条边的权值(也就是距离) while(1) { printf("请输入一个起始景点的编号(%d到%d): ",0,c.vexnum-1); scanf("%d",&v0); //景点图有c.vexnum个顶点,编号从0到(c.vexnum-1) if(v0= c.vexnum) { printf("景点的编号不存在!请重新输入编号
"); continue; //直接跳到while()语句,继续循环 } else { break; } } //对数组D和数组P进行初始化 for(v=0; v (D[v][k]+D[k][w]) ) { //如果经过下标为k顶点路径比原两点间路径更短, //那么,就将当前两点间权值设为更小的一个路径设置为经过下标为k的顶点 D[v][w]=D[v][k]+D[k][w]; P[v][w]=P[v][k]; } } } } v=v0; //v0是起始顶点编号 for(w=0; w%s",c.vexs[k].name); //打印路径"经过的顶点"的名称 k=P[k][w]; //获得"下一个"路径顶点下标 } printf("-->%s",c.vexs[w].name); //打印"终点"的名称 printf(" 总路线长%dm",D[v][w]); printf("
"); }}//输出任意一点与其它各点的最短路径//算法: 迪杰斯特拉(Dijkstra)void allpath_Dijkstra(mgraph c){ int v0; //输入的起始顶点编号 int w0; int v,w,k,min; int qty; int finalData[MaxVertexNum]; //finalData[w]=1表示已经求得起始顶点v0到vw(w是下标)的最短路径 int P[MaxVertexNum]; //数组P用于记录两点之间的路径下标 int D[MaxVertexNum]; //数组D用于存储到各点最短路径的权值和 int PathBuf[MaxVertexNum]; //存入按顺序的路径下标(用于屏幕显示) while(1) { printf("请输入一个起始景点的编号(%d到%d): ",0,c.vexnum-1); scanf("%d",&v0); //景点图有c.vexnum个顶点,编号从0到(c.vexnum-1) if(v0= c.vexnum) { printf("景点的编号不存在!请重新输入编号
"); continue; //直接跳到while()语句,继续循环 } else { break; } } for(v=0; v =1 ; k--) { printf("%s-->",c.vexs[PathBuf[k]].name); } printf("%s",c.vexs[PathBuf[k]].name); printf(" 总路线长%dm",D[w0]); printf("
"); }}int main(void){ //创建景点图 initgraph(&c); //输入参数是指针 //查看景点间的路线 allpath_Floyd(c); //方案1: Floyd算法 //allpath_Dijkstra(c); //方案2: Dijkstra算法 //allpath(c); //原代码[需要改善]return 0;}
int line;//结点之间的路径数
int n ; //实际结点数，我们通过键盘输入
const int maxnum = 15; //支持的最大节点数
int cost[maxnum][maxnum] = {0}; //两点之间的直线距离,最好初始化为无穷大
int s[maxnum] = {0}; //s 判断结点是否在s集合里
int dist[maxnum]; // 表示当前点到源点的最短路径长度
int path[maxnum][maxnum];
int MINDIST(int s[],int dist[])
{
int temp=100000 , i, w = 2;
for(i = 2;i <= n; i++)
{
if(s[i] == 0 && dist[i] < temp)
{
temp = dist[i];
w = i;
}
}
return w;
}
int SEARCH_VER(int s[],int dist[],int u)
{
static int j = 0;
for(; j<=n; )
if(s[j] == 0 && cost[u][j]<100000)
{
j++;
return j-1;
}
else
{
j++;
}
return -1;
}
void SHORTEST_PATH(int cost[][maxnum],int v,int last,int dist[],int path[][maxnum])
{
int i,w,u,count,pos[maxnum];
for(i=0;i<n;i++)
{
s[i]=0;
dist[i]=cost[v][i];
path[i][0]=v;
pos[i]=0;
}
s[v]=1;
count=1;
while(count<=last)
{
u=MINDIST(s,dist);
s[u]=1;
path[u][++pos[u]]=u;
count++;
while(1)
{
if((w=SEARCH_VER(s,dist,u))==-1)
break;
else
{
if(dist[u]+cost[u][w]<dist[w])
{
dist[w]=dist[u]+cost[u][w];
for(i=0;i<pos[u];i++)
path[w][i]=path[u][i];
}
}
}
}
}
int main(int argc, char* argv[])
{
printf("请输入结点数:");
scanf("%d",&n);
printf("请输入路径数:");
scanf("%d",&line);
printf("请输入结点之间的权值\n结点1,结点2,权值\n");
int ii,jj;
for (int i = 0;i<line;i++)
{
cost[ii][jj] = 100000;
dist[i] = 100000;
scanf("%d%d%d",&ii,&jj,&cost[ii][jj]);
}
SHORTEST_PATH(cost,0,n-1,dist,path);
for (i = 0;i<n;i++)
for (int j = 0;j<n;j++)
{
printf("%d\n",path[i][j]);
}
return 0;
}
你能不能告诉我这个path是做什么用的吗？我研究了一下午，只研究了这么多，但是path是做什么用的，我真的不知道，我可以改成其他的实现方法吗？
数据结构有错误 需要修改
守巩甘氨： 给定一个有向图,求v1到其他各节点的最短路径长度,以及最短路径.要求:对dijkstra算法进行补充,使新算法在找出这些最短路径长度的同时,也能求出路径上的节点序列.输入:一个有向带权图 这里写图片描述 输出的基本形式如下:这里写图片描述
山东省19158174091： 用C或C++实现求最短路径的Dijkstra算法 - ？
守巩甘氨： /* 用邻接矩阵表示的图的Dijkstra算法的源程序*/ #include #define MAXVEX 100 typedef char VexType; typedef float AdjType; typedef struct { VexType vexs[MAXVEX]; /* 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ int n; /* 图的...
山东省19158174091： 迪杰斯特拉算法的通俗描述 - ？
守巩甘氨： Dijkstra算法如果不用斐波那契堆优化的话,一般是没有加了SLF的SPFA快.而且局限性太大(要求边权为正),普适性差.
山东省19158174091： 编写的迪杰斯特拉算法求最短路径,运行不正确? - ？
守巩甘氨： 鉴于最小生成树和最短路径的dijkstra是相似的,我把它们合到一块了,另外下面附了一个用堆优化的dijkstra(优先队列)的代码,看看吧.最小生成树的普利姆算法和求最短路径的dijkstra算法 算法思想:1.、先将出发点(对最小生成树来说可...
山东省19158174091： 数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题 - ？
守巩甘氨： 1. dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2. 按dij算法求求看.2.这句话还没找到反例...不过教floyd时说是用在非负权边上的,除了负的回路之外应该还有漏洞吧..
山东省19158174091： Dijkstrath算法是什么?如何用Dijkstrath算法求计算机网络拓扑图的最短路径?？
守巩甘氨： Dijkstra算法是典型 的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的...
山东省19158174091： 这个C++程序运行时总有错误,错误发生在Dijstra算法中,求高手解决,是有关数据结构迪杰斯特拉算法的 - ？
守巩甘氨： 1、你的dijskra算法在找到一个最近节点之后只更新了距离,没有更新记录前驱节点的数组path.2、显示路径的函数里面start和end是什么东东能说下么
山东省19158174091： 求编程领域上一些经典算法同时也是程序员必须掌握的算法 - ？
守巩甘氨： 这是我在一个论坛里看到的,你也参考参考吧.C++的虚函数====================== C++使用虚函数实现了其对象的多态,C++对象的开始四个字节是指向虚函数表的指针,其初始化顺序是先基类后派生类,所以该虚函数表永远指向最后一...
山东省19158174091： 最短路径算法 Dijkstra 用C语言编出来 - ？
守巩甘氨： #include＂iostream.h＂#include＂stdlib.h＂#define MAXPOINT 3//定义最大的顶点数目#define limit 32767 //设置没有路径的权代替无穷大struct record{ //没个顶点的数据结构设置为一个数组队列int number; //顶点号int flag; //标志是否从队列中...
山东省19158174091： C语言数据结构关于dijkstra算法 - ？
守巩甘氨： 你用一个数组 dist 记录最短路径长,用另一个数组 pre 记录直接前驱.关键语句如下: if (dist[j] > dist[i] + edge[i, j]) {dist[j] = dist[i] + edge[i, j];pre[j] = i; } 这样就行了.
