dijkstra.cpp

最小路径算法

#include<iostream>
using namespace std;
#define INF 65536 //无穷大 
#define MAXV 6
int graph[MAXV][MAXV]={{INF,INF,INF,INF,INF,INF},   //有向图的邻接矩阵表示 
                       {INF,INF,INF,INF,INF,INF},
                       {INF,INF,INF,INF,INF,INF},
                       {INF,INF,INF,INF,INF,INF},
                       {INF,INF,INF,INF,INF,INF},
                       {INF,INF,INF,INF,INF,INF}};

void ppath(int path[],int i,int v0)
{
    int k;
    k=path[i];
    if(k==v0) return;
    ppath(path,k,v0);
    cout<<k<<" ";
}
//输出从源点到每一个可达点的距离
void PrintPath(int dis[],int path[],int s[],int n,int v0)
{
    int i;
    for(i=1;i<n;i++)
    {
        if(s[i]==1)
        {
            cout<<"从"<<v0<<"到"<<i<<"的最短路径长度为:"<<dis[i]<<" ";
            cout<<v0<<" ";
            ppath(path,i,v0);
            cout<<i<<endl;
        }else{
            cout<<"从"<<v0<<"到"<<i<<"的路径不存在\n";
        }         
    }
}                 

void InputDistant(int n)
{
	int p, q, dist;
	cout << "输入各节点间距离(节点 节点 距离): ";
	for ( int i = 0; i < n; i++ )
	{
		cin >> p ;
		cin >> q ;
		cin	>> dist;
		graph[p][q] = dist;
		graph[q][p] = dist;
	}
}

void Dijkstra(int n,int v0) //n为顶点个数,v0为源点 
{
    int  dis[MAXV],   //distance[i]保存从源点到终点vi目前最短路径的长度 
        path[MAXV];   //path[i]保存从源点v0到终点vi当前最短路径中前一个顶点的编号 
    int s[MAXV];      //已找到时最短路径的点 
    int mindis,i,j,u;
    
    for(i=0;i<n;i++)  //距离初始化 
    {
        dis[i]=graph[v0][i];
        s[i]=0;
        if(graph[v0][i]<INF){
            path[i]=v0;
        }else{
            path[i]=-1;
        }
    }
    
    s[v0]=1;
    path[v0]=0;
    for(i=0;i<n;i++)
    {
        //选取不在S中且有最小距离的顶点u
        mindis=INF;
        u=-1;
        for(j=0;j<n;j++){   
            if(s[j]==0&&dis[j]<mindis)
            {
                u=j;
                mindis=dis[j];
            }
        }    
        s[u]=1;   
        //修改不在S中的顶点的距离      
        for(j=0;j<n;j++){
            if(s[j]==0){
                if(graph[u][j]<INF&&dis[u]+graph[u][j]<dis[j]){
                    dis[j]=dis[u]+graph[u][j];
                    path[j]=u;
                }                
            }  
        }
    }
    //输出最短路径 
    PrintPath(dis,path,s,n,v0);            
}    
int main()
{
	int node, vex;
	cout << "输入顶点数: " ;
	cin >> node ;
	cout << "输入边数: ";
	cin >> vex;


	InputDistant(vex);

    Dijkstra(node, 0);
    system("pause");
    return 0;
}