[C++知识库]数据结构之C++实现最短路径迪杰特斯拉(dijkstra)算法

数据结构之C++实现最短路径迪杰特斯拉(dijkstra)算法.md

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include "sys/io.h"
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define GRAPH_INFINITY 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
class MGraph
{
public:
    MGraph();
    //~MGraph();
    void CreatMGraph(void);/* 构建图 */
    void ShortestPath_Dijkstra(int v0);
    void show(void);
public:
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
    int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
    int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */
};
MGraph::MGraph()
{
    for (int i = 0; i < MAXVEX; i++)/* 初始化图 */
    {
        vexs[i]=i;
    }

    for (int i = 0; i < MAXVEX; i++)/* 初始化图 */
    {
        for (int j = 0; j < MAXVEX; j++)
        {
            if (i==j)
                arc[i][j]=0;
            else
                arc[i][j] = arc[j][i] = GRAPH_INFINITY;
        }
    }
}
void MGraph::CreatMGraph(void)
{
    int i, j;

    /* printf("请输入边数和顶点数:"); */
    numEdges=16;
    numVertexes=9;

    arc[0][1]=1;
    arc[0][2]=5; 
    arc[1][2]=3; 
    arc[1][3]=7; 
    arc[1][4]=5; 

    arc[2][4]=1; 
    arc[2][5]=7; 
    arc[3][4]=2; 
    arc[3][6]=3; 
    arc[4][5]=3;

    arc[4][6]=6;
    arc[4][7]=9; 
    arc[5][7]=5; 
    arc[6][7]=2; 
    arc[6][8]=7;

    arc[7][8]=4;


    for(i = 0; i < numVertexes; i++)
    {
        for(j = i; j < numVertexes; j++)
        {
            arc[j][i] =arc[i][j];
        }
    }
}
/*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
/*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
void MGraph::ShortestPath_Dijkstra(int v0)
{
    int v,w,k,min;    
    int final[MAXVEX]; /*final[w]=1表示求得顶点v0至vw的最短路径 */
    for(v=0; v<numVertexes; v++)/* 初始化数据 */
    {        
        final[v] = 0;           /* 全部顶点初始化为未知最短路径状态 */
        ShortPathTable[v] = arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
        Patharc[v] = -1;               /* 初始化路径数组P为-1  */       
    }
    ShortPathTable[v0] = 0;  /* v0至v0路径为0 */  
    final[v0] = 1;    /* v0至v0不需要求路径 */        
    /*开始主循环，每次求得v0到某个v顶点的最短路径*/   
    for(v=1; v<numVertexes; v++)   
    {
        min=GRAPH_INFINITY;    /* 当前所知离v0顶点的最近距离 */        
        for(w=0; w<numVertexes; w++) /*寻找离v0最近的顶点 */    
        {            
            if(!final[w] && ShortPathTable[w]<min)             
            {                   
                k=w;                    
                min = ShortPathTable[w];    /* w顶点离v0顶点更近 */            
            }        
        }        
        final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
        for(w=0; w<numVertexes; w++) /* 修正当前最短路径及距离 */
        {
            /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
            if(!final[w] && (min+arc[k][w]<ShortPathTable[w]))   
            { /*  说明找到了更短的路径，修改D[w]和P[w] */
                ShortPathTable[w] = min + arc[k][w];  /* 修改当前路径长度 */               
                Patharc[w]=k;        
            }       
        }   
    }
    
}
void MGraph::show(void)
{
    cout<<"vexs is ";
    for(int i=0;i<numVertexes;i++)
    {
        cout<<vexs[i]<<" ";
    }
    cout<<endl<<"arc is "<<endl;
    for(int i=0;i<numVertexes;i++)
    {
        for(int j=0;j<numVertexes;j++)
        {
            cout<<arc[i][j]<<"     ";
        }
        cout<<endl;
    }
}
int main()
{
    int i,j,v0;
    MGraph *G=new MGraph;
    v0=0;
    G->CreatMGraph();
    G->show();
    G->ShortestPath_Dijkstra(v0);
    cout<<"最短路径倒序如下:"<<endl;
    for(i=1;i<G->numVertexes;++i)   
    {    
        cout<< "v"<<v0<<" - v"<<i<<" : ";  
        j=i;
        while(G->Patharc[j]!=-1)
        {
            cout<<G->Patharc[j]<<" ";
            j=G->Patharc[j];
        }
        cout<<endl;
    }
    cout<<endl<<"源点到各顶点的最短路径长度为:"<<endl;
    for(i=1;i<G->numVertexes;++i) 
        cout<<"v"<<G->vexs[0]<<" - v"<<G->vexs[i]<<" : "<<G->ShortPathTable[i]<<endl;
    delete G;
    return 0;
}