Dijkstra算法单源最短路径
使用邻接表存储图,最短路径的保存使用并查集。
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
#define INF 9999999
/*
邻接表定义
*/
typedef struct ArcNode{
int data;
struct ArcNode *nextArc;
int info;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstArc;
}VNode,Adjlist;
typedef struct ALGraph{
Adjlist vertices[MAXSIZE];
int vexnum,arcnum;
}ALGraph;
/*
创建图(邻接表存储)
*/
void CreateALGraph(ALGraph &g){
cout<<"Now create ALGraph: vexnum arcnum"<<endl;
cin>>g.vexnum>>g.arcnum;
for(int i=1;i<=g.arcnum;i++){
g.vertices[i].firstArc=NULL;
g.vertices[i].data=i;
}
//输入边
cout<<"Now input the arcs:"<<endl;
for(int i=0;i<g.arcnum;i++){
//cout<<"input arc"<<i+1<<":";
int u,v,info;
cin>>u>>v>>info;
if (g.vertices[u].firstArc==NULL){
//cout<<"new firstArc"<<endl;
ArcNode *q=(ArcNode*)malloc(sizeof(ArcNode));
q->data=v;
q->info=info;
q->nextArc=NULL;
g.vertices[u].firstArc=q;
}
else{
ArcNode *p=g.vertices[u].firstArc;
while (p->nextArc!=NULL){
p=p->nextArc;
}
ArcNode *q=(ArcNode*)malloc(sizeof(ArcNode));
q->data=v;
q->info=info;
q->nextArc=NULL;
p->nextArc=q;
}
}
//输出邻接表
cout<<endl<<"Now output arcs info:"<<endl;
for (int i = 1; i <= g.vexnum; i++){
cout<<"vertex "<<g.vertices[i].data<<" :";
ArcNode *p=g.vertices[i].firstArc;
while (p!=NULL){
cout<<p->data<<" ";
p=p->nextArc;
}
cout<<endl<<endl;
}
}
int visited[MAXSIZE];
int dist[MAXSIZE];
int path[MAXSIZE];
/*
清空visited[]
*/
void clearVisited(){
for(int i=0;i<MAXSIZE;i++){
visited[i]=0;
}
}
void Dijkstra(ALGraph g,int u){
for(int i=1;i<=g.vexnum;i++){ //初始化
visited[i]=0;
path[i]=-1;
dist[i]=INF;
}
dist[u]=0;
while (1){
int min=-1;
int mind=INF;
for (int i = 1; i < g.vexnum; i++)
{
if(!visited[i]&&dist[i]<mind){
min=i;
mind=dist[i];
}
}
if(min==-1)
break;
cout<<"select min"<<min<<endl;
visited[min]=1;
ArcNode *p=g.vertices[min].firstArc;
while (p)
{
if(!visited[p->data]&&mind+p->info<dist[p->data]){
cout<<"find shorter"<<p->data<<endl;
dist[p->data]=mind+p->info;
path[p->data]=min;
}
p=p->nextArc;
}
}
for(int i=1;i<=g.vexnum;i++){
cout<<dist[i]<<" ";
}
cout<<endl;
}
int main(){
ALGraph g;
CreateALGraph(g); //创建图
Dijkstra(g,1);
return 0;
}
/*
6 16
1 2 7
1 3 11
2 4 9
2 3 10
3 4 5
3 5 7
3 6 8
5 6 6
6 5 6
6 3 8
5 3 7
4 3 5
3 2 10
4 2 9
3 1 11
2 1 7
*/