算法思想:
辅助数组dis[i] 表示当前源顶点到i的最短路径。dis[i]在程序未结束前,类似于动态规划,可更新以取得最小值
数组path用来记录路径
首先初始化令dis[i]为Edge[v0][i],v0为源顶点,然后选择离源顶点最小的路径,加入到构造最短路径的点集合中,然后看是否可以更新dis[i]的值,依次循环n-1次,即可得打正解.
测试代码:
#include<iostream>
#include<cstring>
#include<stack>
#define MAX 1000
#define M 100
#define N 100
using namespace std;
int Edge[M][N];
void Dijkstra(int *path,int *dis,int v0,int n);
void showPath(int *path,int v,int v0);
int main()
{
cout<<"请输入顶点数与边数"<<endl;
int n,e;
cin>>n>>e;
int i,x,y,z,j;
for(i=0;i<=n;++i) for(j=0;j<=n;++j) Edge[i][j]=MAX;
for(i=0;i<e;++i)
{
cin>>x>>y>>z;
Edge[x][y]=Edge[y][x]=z;
}
int path[n+1];
int dis[n+1];
Dijkstra(path,dis,1,n);
for(int q=2;q<=n;++q)
{
showPath(path,q,1);
cout<<dis[q]<<endl;
}
system("pause");
return 0;
}
void Dijkstra(int *path,int *dis,int v0,int n)
{
bool visited[n+1];
int i,j,k;
for(i=2;i<=n;++i)
{
visited[i]=false;
dis[i]=Edge[1][i];
path[i]=1;
}
visited[1]=true;
path[1]=1;
for(j=1;j<n;++j)
{
int min=MAX,q;
for(k=1;k<=n;++k)
if(dis[k]<min&&visited[k]==false)
{ min=dis[k]; q=k;}
visited[q]=true;
for(i=1;i<=n;i++)
{
if(visited[i]==false&&dis[i]>min+Edge[q][i])
{ dis[i]=min+Edge[q][i];path[i]=q;}
}
}
}
void showPath(int *path,int v,int v0)
{
stack<int> s;
int u=v;
while(v!=v0)
{
s.push(v);
v=path[v];
}
s.push(v);
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
}