http://www.bjfuacm.com/problem/273/
#include<iostream>
using namespace std;
#include <cstdio> //freopen函数在这个文件中
#define MAXSIZE 100
#define OK 1
typedef int Status;
//用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum;//图的总点数
int arcnum;//图的总边数
}AMGraph;
int LocateVex(AMGraph G,VerTexType u)
{//存在则返回u在顶点表中的下标;否则返回-1
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i])
return i;
return -1;
}
VerTexType OrigialVex(AMGraph G,int u)
{//存在则返回u在顶点表中的下标;否则返回-1
return G.vexs[u];
}
int goal;
Status CreateUDN(AMGraph &G){
//采用邻接矩阵表示法，创建无向网G
cin>>G.vexnum; //输入总顶点数
cin>>G.arcnum; //输入总边数
int i,j,k,w;
VerTexType v1,v2;
for(i = 0; i<G.vexnum; ++i)
cin>>G.vexs[i]; //依次输入点的信息
for(i = 0; i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值
for(j = 0; j<G.vexnum;++j)
G.arcs[i][j] = MaxInt;
for(k = 0; k<G.arcnum;++k){ //构造邻接矩阵
cin>>v1>>v2>>w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w
}//for
return OK;
}//CreateUDN
Status CreateDN(AMGraph &G,int dian,int bian){
//采用邻接矩阵表示法，创建有向网G
//cin>>G.vexnum; //输入总顶点数
//cin>>G.arcnum; //输入总边数
G.vexnum=dian;
G.arcnum=bian;
int i,j,k,w;
VerTexType v1,v2;
for(i = 0; i<G.vexnum; ++i)
cin>>G.vexs[i]; //依次输入点的信息
for(i = 0; i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值
for(j = 0; j<G.vexnum;++j)
G.arcs[i][j] = MaxInt;
for(k = 0; k<G.arcnum;++k){ //构造邻接矩阵
cin>>v1>>v2>>w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
}//for
return OK;
}//CreateDN
int D[MVNum],Path[MVNum];
void ShortestPath_DIJ(AMGraph G, VerTexType V){
//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
int i,n,v,min,w;
int S[MVNum];
n=G.vexnum; //n为G中顶点的个数
int v0=LocateVex(G,V);
for(v = 0; v<n; ++v)
{ //n个顶点依次初始化
S[v] = false; //S初始为空集
D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化
if(D[v]< MaxInt)
Path [v]=v0; //v0和v之间有弧，将v的前驱置为v0
else
Path [v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1
}//for
S[v0]=true; //将v0加入S
D[v0]=0; //源点到源点的距离为0
/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/
for(i=1;i<n; ++i)
{ //对其余n−1个顶点，依次进行计算
min= MaxInt;
for(w=0;w<n; ++w)
if(!S[w]&&D[w]<min)
{
v=w; min=D[w];
} //选择一条当前的最短路径，终点为v
S[v]=true; //将v加入S
for(w=0;w<n; ++w) //更新从v0出发到集合V−S上所有顶点的最短路径长度
if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){
D[w]=D[v]+G.arcs[v][w]; //更新D[w]
Path [w]=v; //更改w的前驱为v
}//if
}//for
//for(int i=0;i<n;i++)
//cout<<Path[i]<<" ";
//cout<<endl;
}//ShortestPath_DIJ
void find(AMGraph G,int v)
{
int n=G.vexnum;
if(Path[v]==-1)
return;
else
{
find(G,Path[v]);
cout<<OrigialVex(G,Path[v])<<" ";
}
}
int main()
{
#ifndef ONLINE_JUDGE //if not define 如果没有定义这个的话就执行下面
//freopen("input.txt", "r", stdin); //只改变输入流的文件指针，读入这个文件的内容（必须要有input这个文件）stdin是标准输入流的文件指针
//freopen("output.txt", "w", stdout); //只改变输出流的文件指针，写入output内（如果没有output这个文件就会自动生成）stdout是标准输出流的文件指针
#endif
char A,B;
int a,b;
while(cin>>a>>b&&a&&b){
AMGraph G;
CreateDN(G,a,b);
cin>>A;
ShortestPath_DIJ(G,A);
cin>>B;
int n=LocateVex(G,B);
cout<<D[n]<<endl;
find(G,n);
cout<<B<<endl;
}
return 0;
}
基于Dijsktra算法的最短路径求解
发布时间: 2017年9月18日 10:30 最后更新: 2017年9月19日 02:53 时间限制: 1000ms 内存限制: 128M
描述
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。
输入
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。
输出
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。
样例输入1
3 3
A B C
A B 1
B C 1
A C 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
E D 20
E F 60
D F 10
A F
0 0
样例输出1
2
A B C
60
A E D F
网友评论