#include <stdlib.h>
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define MAX 10
void dijkstra(int G[MAX][MAX],int n,int startnode)//n为顶点个数
{
int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,i,j;
//pred[] 记录前驱结点
//count记录已经找到最短路径的结点个数 visited[]标记到该点是否已找到最短路径，1为已找到
//设置权值
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
//初始化 pred[],distance[],visited[]
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];///distance是开始结点到每个顶点的距离
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=INFINITY;
int u = startnode;// 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if(visited[j]==0 && distance[j]<mindistance)
{
u = j; // u保存当前邻接点中距离最小的点的号码
mindistance = distance[j];
}
visited[u]=1 ;
for(int j=1; j<=n; j++)
if( visited[j]==0 && cost[u][j]<INFINITY)//如果该点还没有找到最短路径，且和u点之间可达
{
if(distance[u] + cost[u][j] < distance[j]) //在通过新加入的u点路径找到离v0点更短的路径
{
distance[j] = distance[u] + cost[u][j]; //更新distance
pred[j] = u; //记录前驱顶点
}
}
count++;
}
//输出路径和结点
for(i=0;i<n;i++)
if(i!=startnode)
{
printf("\n结点%d和结点%d之间的最小距离是%d",startnode,i,distance[i]);
printf("\n路径：%d",i);
j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
printf("\n");
}
}
int main()
{
int n,m;//顶点个数
int G[MAX][MAX];
int i,j;
cout<<"请输入结点数量："<<endl;
cin>>n;
cout<<"请输入开始的结点："<<endl;
cin>>m;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
G[i][j]=rand()%50;
cout<<"结点之间的距离关系（结点1 结点2 距离）为："<<endl;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cout<<i<<" "<<j<<" "<<G[i][j]<<endl;
dijkstra(G,n,m);//G为带权无向图，n为顶点个数，0为开始结点
system("pause");
return 0;
}
评论0