最短路径之Dijkstra算法

考虑如下无向网（假设从v0出发）:

最短路径数组变化情况：

/**************************************
迪杰斯特拉算法求最短路径
by Rowandjj
2014/7/10
**************************************/

#include<iostream>
using namespace std;


#define INFINTY 65535
#define MAX_INFO 20
#define MAX_VERTEX_NUM 20

typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];


typedef struct _ARC_
{
    int adj;//顶点关系类型
    char *info;
}AdiMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct _GRAPH_//图的邻接矩阵存储形式
{
    char vexs[MAX_VERTEX_NUM];
    AdiMatrix arcs;
    int arcnum,vexnum;
}Graph;
//-----------------------
int LocateVex(Graph G,char u);
void CreateDN(Graph *G);
void Display(Graph G);

void ShortestPath_DIJ(Graph G,int v0,PathMatrix *P,ShortPathTable *D);
//---------------------------------------------
int main()
{
    Graph g;
    CreateDN(&g);
    Display(g);

    PathMatrix p;
    ShortPathTable d;
    ShortestPath_DIJ(g,0,&p,&d);
    int i,j;
    printf("最短路径数组p[i][j]如下:\n");
    for(i=0;i<g.vexnum;++i)
    {
        for(j=0;j<g.vexnum;++j)
            cout<<p[i][j]<<"\t";
        cout<<endl;
    }
    cout<<"到各顶点的最短路径长度为:"<<endl;
    for(i=1;i<g.vexnum;++i)
        cout<<g.vexs[0]<<"-->"<<g.vexs[i]<<":"<<d[i]<<endl;
    return 0;
}

//--------------------------------------------
int LocateVex(Graph G,char u)
{
    int i = 0;
    for(i = 0; i < G.vexnum;i++)
    {
        if(u == G.vexs[i])
        {
            return i;
        }
    }
    return -1;
}
void CreateDN(Graph *G)//构建有向网
{
    int incInfo;
    int i,j,k,l,w;
    char s[MAX_INFO];
    cout<<"请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)"<<endl;
    cin>>G->vexnum;
    cin>>G->arcnum;
    cin>>incInfo;
    char va,vb;//分别代表弧头、弧尾
    char *pInfo;
    
    cout<<"请输入顶点值"<<endl;
    for(i = 0; i < G->vexnum; i++)
    {
        cin>>G->vexs[i];
    }
    for(i = 0; i < G->vexnum; i++)
    {
        for(j = 0; j < G->vexnum; j++)
        {
            G->arcs[i][j].adj = INFINTY;//网
            G->arcs[i][j].info = NULL;
        }
    }
    
    cout<<"请输入弧尾、弧头、权值"<<endl;
    for(k = 0; k < G->arcnum; k++)
    {
   
        cin>>va;
        cin>>vb;
        cin>>w;
        i = LocateVex(*G,va);
        j = LocateVex(*G,vb);
        
        G->arcs[i][j].adj = w;
        if(incInfo)
        {
            cout<<"请输入该弧的信息"<<endl;
            cin>>s;
            l = strlen(s);
            if(l)
            {
                pInfo = (char *)malloc(sizeof(char)*(l+1));
                strcpy(pInfo,s);
                G->arcs[i][j].info = pInfo;
            }
        }
        
    }
}

void Display(Graph G)
{
    int i,j;
    for(i = 0; i < G.vexnum; i++)
    {
        for(j = 0; j < G.vexnum; j++)
        {
            cout<<G.arcs[i][j].adj<<"\t";
        }
        cout<<endl;
    }
    cout<<endl;
}

void ShortestPath_DIJ(Graph G,int v0,PathMatrix *P,ShortPathTable *D)
{
    int v,w,i,j,min;
    int final[MAX_VERTEX_NUM];
    for(v=0;v<G.vexnum;++v)
    {
        final[v]=0;
        (*D)[v]=G.arcs[v0][v].adj;
        for(w=0;w<G.vexnum;++w)
            (*P)[v][w]=0; /* 设空路径 */
        if((*D)[v]<INFINTY)
        {
            (*P)[v][v0]=1;
            (*P)[v][v]=1;
        }
    }
    (*D)[v0]=0;
    final[v0]=1; /* 初始化,v0顶点属于S集 */
    
    for(i=1;i<G.vexnum;++i) /* 其余G.vexnum-1个顶点 */
    { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
        min=INFINTY; /* 当前所知离v0顶点的最近距离 */
        for(w=0;w<G.vexnum;++w)
        {
            if(!final[w]) /* w顶点在V-S中 */
            {
                if((*D)[w]<min)
                {
                    v=w;
                    min=(*D)[w];
                } /* w顶点离v0顶点更近 */
            }        
        }
        
        final[v]=1; /* 离v0顶点最近的v加入S集 */
        for(w=0;w<G.vexnum;++w) /* 更新当前最短路径及距离 */
        {
            if(!final[w]&&min<INFINTY&&G.arcs[v][w].adj<INFINTY&&(min+G.arcs[v][w].adj<(*D)[w]))
            { /* 修改D[w]和P[w],w∈V-S */
                (*D)[w]=min+G.arcs[v][w].adj;
                for(j=0;j<G.vexnum;++j)
                    (*P)[w][j]=(*P)[v][j];
                (*P)[w][w]=1;
            }
        }
   }
}

最短路径之Dijkstra算法,布布扣,bubuko.com

最短路径之Dijkstra算法

原文：http://blog.csdn.net/chdjj/article/details/37662885