用C++编译Dijkstra算法
输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示
当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点
比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径
Dijkstra算法的完整实现版本，算法的源代码
/* Dijkstra.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!
");
printf("Please input the number of points:
");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("
Number of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:
",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex[0]='v';
lin->vertex[1]='0'+temp;
lin->vertex[2]='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:
");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i<total;i++)
{
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex[1]==now->vertex[1])
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex[1];
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path[0]='v';
searc->path[1]=now->vertex[1];
searc->path[2]='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost<min)
{
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex[1]-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex[1]-'0')!=start&&p!=NULL)
{
while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("
%s",p->vertex);
return OK;
}
#include
#define INF 1000000000
#define MAXV 200
typedef struct Graph{
int n;
int w[MAXV][MAXV];
};
int d[MAXV];
int pre[MAXV];
void init_single_source(Graph *G,int s) {
for (int i=0;in;i++) {
d[i]=INF;
pre[i]=-1;
}
d[s]=0;
}
void relax(int u,int v,Graph *G) {
if (d[v]>d[u]+G->w[u][v]) {
d[v]=d[u]+G->w[u][v];
pre[v]=u;
}
}
int dijkstra(Graph *G,int s) {
init_single_source(G,s);
int S[MAXV],i,j,u,min;
for (i=0;in;i++) S[i]=0;
for (i=0;in;i++) {
min=INF;
u=-1;
for (j=0;jn;j++) if (S[j]==0 && d[j]<min) {
u=j;
min=d[j];
}
S[u]=-1;
for (j=0;jn;j++) if (S[j]==0) relax(u,j,G);
}
}
#define inf 999999
#define maxn 101
using namespace std;
int n,node1,node2,d;
int dist[maxn],prev[maxn],c[maxn][maxn];//分别是记录最短距离，最短路径的前驱，各点之间的距离
void disktra(int v)//原点是v
{
bool s[maxn]; register int i,j,k;
for(i=1;i<=n;i++){
dist[i] = c[v][i];
s[i] = 0; // i不在集合S中
if(dist[i]==inf)//v to i没有边
prev[i] = 0;
else
prev[i] = v;
}
s[v] = 1; dist[v] = 0;
for(i=1;i<n;i++){//个一个找；
int temp = inf, u = v;
for(j=1;j<=n;j++)//找出下一个最佳选项
if(!s[j]&&dist[j]&&dist[j]<temp){
u = j;
temp = dist[j];
}
s[u] = 1;
for(j=1;j<=n;j++)//找出下下一个的最佳选项
if(!s[j]&&c[u][j]<inf){
int newdist = dist[u] + c[u][j];
if(newdist < dist[j]){
dist[j] = newdist;
prev[j] = u;
}
}
}
}
int main()
{
cout<<""<<endl;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
c[i][j]=inf;//初始化所有点两两之间距离为999999 相当于无穷
while(cin>>node1>>node2>>d)
if(c[node1][node2]>d)//可能两点之间有不同的边 选择最短的储存
c[node1][node2]=c[node2][node1]=d;
int startpoint=1,endpoint=6; //你可以选择其他起点 或终点
disktra(startpoint);//以1作为起点
cout<<dist[endpoint] <<endl;
cout<<dist[endpoint]<<"->";
while(prev[endpoint]!=startpoint)
{
cout<<prev[endpoint]<<"->";
endpoint=prev[endpoint];
}
cout<<startpoint<<endl;
system("pause");
}
这题请输入
6
1 2 2
1 3 5
1 4 1
2 4 2
2 3 3
3 4 3
3 5 1
3 6 5
4 5 1
4 6 5
自己测试时请按Ctrl+N 结束测试
楼主杯具了，竟然说Dijkstra是动态规划。唉..百度确实没高手。
你用堆优化他也不是动态规划啊。
建议学spfa。
就是说这种东西你想让人给你讲很难。因为太简单了
这个有点麻烦。。。
记得数据结构c语言版书上有程序啊。。
倒。。。
数据结构(C语言版)/严蔚敏/
这本书，第几页忘了，楼主没书？？
Dijkstra（中文：迪杰斯特拉） 是一个典型的动态规划算法
你可以参考：http://baike.baidu.com/view/1712262.htm?fr=ala0_1
如果有想法就写写看
LZ把你邮箱发来 我把书的PDF 发给你 还有我以前做的程序
蓬叔乙酰： Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪 /*********************************************** 设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘. 单源最短路径问题,或者称为最短路径问题...
盐池县18064012573： 用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; /* 图的...
盐池县18064012573： 优先队列实现dijkstra算法C++代码 - ？
蓬叔乙酰： 模板是HDOJ 2544 我写的是记录每个点在堆中的位置IncreaseKey,也可以Relax后直接往里插,用个bool数组记录一下#include<cstdio>#include<cstdlib> int n,m; int map[101][101],d[101]; class Heap { public: int handle[101]; void Build(int n) { for(...
盐池县18064012573： 关于求最短路径的Dijkstra算法的程序源代码 - ？
蓬叔乙酰： 下面是在百度上找到的一篇,已经发到你的邮箱里面了:) Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪 /*********************************************** 设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异...
盐池县18064012573： 如何修改dijkstra算法求多条的最短路径 - ？
蓬叔乙酰： 设有n个点,起点为s,终点为t,d1[i]表示s到i间的最短距离,d2[i]为t到i的最短距离.跑两遍最短路,从起点跑一次,终点跑一次,求出数组d1,d2,即求出1~n离s的距离和1~n到t的距离.对于每一条边,起点为x,终点为y,边权为w,若满足d1[x]+w+d2[y]==len.即判断该边起点到s的距离,加上该边终点到t的距离,再加上边权,若值等于最短路,则这条边就是由所有最短路构成的图的一条边.对每一条边进行判断,从而求出整个图
盐池县18064012573： 用C++编写Dijkstra算法,用List产生的链表的首地址要放在数组中,可总是提示出错 - ？
蓬叔乙酰： 代码不完整,其他问题无法确认.path[j] = List.begin(); ==>*(path[j]) = *(List.begin());
盐池县18064012573： 跪求最短(长)路径算法,(按要求的)Dijkstra算法C/C++源代码 - ？
蓬叔乙酰： int Locate(MGraph G,VexType v) {for(int i=0;iif(strcmp(v,G.vexs[i])==0) return i; return -1; } void ShortestPath(MGraph G,VexType v,int dist[],int path[]) {//求顶点v到其余各个顶点的最短路径长度,并存放在dist数组中,path数组存放路径 int S[MAX_...
盐池县18064012573： 跪求dijkstra算法的邻接矩阵实现和(邻接表+堆排序)实现(C语言或C++代码)详细点最好 - ？
蓬叔乙酰： # include# include class node { public:int to,dis; bool operator { return dis} node (int t,int d){to=t;dis=d;} }; int dis[maxn]; priority_queue Q; int dijkstra(int s,int t) { memset(dis,127,sizeof(dis)); dis[s]=0; Q.push(node(s,0)); while (!Q.empty()) { node x=Q....
盐池县18064012573： 写一个C++程序 图改用邻接表表示,重写Dijkstra算法 数据结构实验报告 - ？
蓬叔乙酰： 下面这个是我粗略写的,你先看看,如有问题,可以再补充,追问.#include<stdlib.h>#include<stdio.h>#define unlimited 9999999; int map[20][20]; int begin[20]; int nodeNum; int iscaculated[20]; bool isfinish() { bool finish = true; for (int i = 0; i < ...
盐池县18064012573： Dijkstra算法的原理和C的编程实现 - ？
蓬叔乙酰： .Dijkstra算法求单源最短路径 语法:result=Dijkstra(Graph G,int n,int s,int t, int path[]);参数:G:图,用邻接矩阵表示n:图的顶点个数s:开始节点t:目标节点path[]:用于返回由开始节点到目标节点的路径返回值:最短路径长度...
