#define DeBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <
string>
#include <
set>
#include <sstream>
#include <map>
#include <bitset>
using namespace std ;
#define zero {0}
#define INF 2000000000
#define EPS 1e-6
typedef long long LL;
const double PI = acos(-
1.0);
inline int sgn(
double x)
{
return fabs(x) < EPS ?
0 :(x <
0 ? -
1 :
1);
}
/**
* [Dijkstra description]
* @param mp 权值矩阵,从1开始
* @param n 点数
* @param s 起始点
* @param t 终点
* @param path 起始点到各点的路(前驱)
* @return 起点到终点的最短长度
*/
int Dijkstra(
int mp[][
100],
int n,
int s,
int t,
int path[])
{
int i,j,w,minc;
bool visit[
100];
int price[
100];
for(i=
1; i<=n; i++
)
visit[i]=
false;
for(i=
1; i<=n; i++
)
{
price[i]=
mp[s][i];
path[i]=
s;
}
visit[s]=
true;
price[s]=
0;
//path[s]=0;
for(i=
1; i<n; i++
)
{
minc=
INF;
w=
0;
for(j=
1; j<=n; j++
)
if((visit[j]==
false)&&(minc>=
price[j]))
{
minc=
price[j];
w=
j;
}
visit[w]=
true;
for(j=
1; j<=n; j++
)
if((visit[j]==
false)&&(mp[w][j]!=INF)&&(price[j]>price[w]+
mp[w][j]))
{
price[j]=price[w]+
mp[w][j];
path[j]=
w;
}
}
return price[t];
}
void init(
int mp[][
100],
int n)
{
for(
int i=
1;i<=n;i++
)
{
for(
int j=
1;j<=n;j++
)
{
mp[i][j]=
INF;
}
}
}
int main()
{
#ifdef DeBUGs
freopen("C:\\Users\\Sky\\Desktop\\1.in",
"r",stdin);
#endif
int n,m;
int mp[
100][
100];
int path[
100];
while(scanf(
"%d%d",&n,&m)+
1)
{
init(mp,n);
int a,b;
for(
int i=
1; i<=m; i++
)
{
scanf("%d%d",&a,&
b);
mp[a][b]=
1;
mp[b][a]=
1;
}
int s=
1;
int t=
7;
int value=
Dijkstra(mp,n,s,t,path);
for(
int i=
1;i<=n;i++
)
{
int k=
i;
while(k!=
s)
{
printf("%d<--",k);
k=
path[k];
}
printf("%d\n",s);
}
// printf("%d\n",s);
printf(
"%d\n", value);
}
return 0;
}
/*
7 7
1 2
2 3
3 4
1 5
5 7
5 6
2 7
*/
View Code
转载于:https://www.cnblogs.com/Skyxj/p/3463756.html
相关资源：C语言实现Dijkstra算法
