本文主要向大家介绍了C/C++知识点之最短路径Dijkstra算法的C语言实现，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

  本文主要分为两个部分，一是邻接表的创建，二是最短路径问题的实现。将本文中的代码顺序粘贴下来，即可运行。
  在文章的最后有结合实例且比较详细的最短路径算法的执行情况，博主在之前的学习中这部分理解出现了问题，可能其他人在这个地方的理解也会出现偏差，因此我写了结合实例并且较为详细的运算过程。

   以下是关于邻接矩阵的创建


#include<stdio.h>  
#include<stdlib.h> 
#include<malloc.h>

#define MAX 10000
#define MAXVEX 100
#define DEBUG

typedef char VertexType;//顶点类型应该由用户自己定义
typedef int EdgeType;

typedef struct 
{
    VertexType vertex[MAXVEX];
    EdgeType   adjList[MAXVEX][MAXVEX];
    int numVertexes,numEdges;//记录结点个数，边的个数
}Graph; 
void dijkstra(int startPos,int distance[],int path[],Graph *g);                                //求最短路径
void doDijkstra(Graph *g);      
char getValue(int i,Graph *g);  //获取某个编号所对应的顶点
int getNum(char ch,Graph *g);   //获取某个结点的编号
int locates(Graph *g,char ch);  //同样是获取某个结点的编号,同上
int getWeight(int a,int b,Graph *g); //获取某条边的权值


//wenku.baidu.com/link?url=FziBh462uDKGDfZRvGbclA6UtjOGgk4y5N8Jk3vgESMCV7oV0IOG8RMPQQsY_fxM3EwZVrB4C3wy0N6JgJw4bkEQg4UjK28B_dIHreWGTwO  这是一些图常用的英文词汇，便于理解相关语句



int getWeight(int a,int b,Graph *g)
{
    return g->adjList[a][b];
}

下面两个是一样的原谅博主懒得改了



int locates(Graph *g,char ch)
{
    int i=0;
    for(i=0;i<g->numVertexes;i++)
        if(g->vertex[i]==ch)
            break;
    return i;
}



int getNum(char ch,Graph *g)
{
    int i;
    for(i=0;i<g->numVertexes;i++)
        if(g->vertex[i]==ch)
            return i;
}



void createGraph(Graph *g)  //创建一个图
{
    int i,j,k,w;
    printf("Input the number of vertexes and edges.\n");
    scanf("%d,%d",&g->numVertexes,&g->numEdges);//输入图的顶点和边的数目
    for(i=0;i<g->numVertexes;i++)//输入所有顶点
    {
        printf("Please input the vertexes.\n");
        g->vertex[i]=getchar();//循环输入顶点避免回车符号干扰
        while(g->vertex[i]==‘\n‘)
            g->vertex[i]=getchar();
    }
    for(i=0;i<g->numVertexes;i++)//初始化邻接矩阵，将每个值都定为MAX
        for(j=0;j<g->numVertexes;j++)
            g->adjList[i][j]=MAX;
    for(k=0;k<g->numEdges;k++)//输入边（每个边有两个顶点）和权值
    {
        char ch1,ch2;
        printf("Input the edges(vi,vj)coordinate vi ,coordinate vj and weight.\n");
        ch1=getchar();
        while(ch1==‘\n‘)
            ch1=getchar();
        ch2=getchar();
        while(ch2==‘\n‘)
            ch2=getchar();
        scanf("%d",&w);
        int m=-1;
        int n=-1;
        n=locates(g,ch1);
        m=locates(g,ch2);
        g->adjList[m][n]=w;//对邻接矩阵中的边进行赋值
        g->adjList[n][m]=w;
    }
}

void printGraph(Graph *g)//打印邻接矩阵
{
    int i,j;
    for(i=0;i<g->numVertexes;i++)
    {
        for(j=0;j<g->numVertexes;j++)
            printf(" %5d ",g->adjList[i][j]);
        printf("\n");
    }
}



int main()
{
    Graph g;
    createGraph(&g);
    printGraph(&g);
    doDijkstra(&g);//最短路径算法的执行
    printGraph(&g);
    return 0;
}

接下来是最短路径部分源码



void doDijkstra(Graph *g)
{
    char startVertex;
    int *distance,i,*path;
    distance=(int*)malloc(g->numVertexes*sizeof(int));
    path=(int*)malloc(g->numVertexes*sizeof(int));
    printf("We will begin to find the distance from one vertex to the other vertex.\n");
    printf("Please input the starting vertex.\n");
    startVertex=getchar();
    while(startVertex==‘\n‘)
        startVertex=getchar();//输出起始点到其他所有顶点的最短距离
    dijkstra(getNum(startVertex,g),distance,path,g);
    printf("From vertex %c to the other vertexes the shortest distance are.\n",startVertex);
    for(i=0;i<g->numVertexes;i++)
        printf("to vertex %c the distance are: %d\n",getValue(i,g),distance[i]);
    printf("Here is the path.\n");
    for(i=0;i<g->numVertexes;i++)
    {
        if(path[i]!=-1)
            printf("The %c before the vertex is: %c \n",getValue(i,g),getValue(path[i],g));//输出在求最短路径过程中
                       //目标点和路径上它之前的那个点
    }
}

接下来我主要讲讲最短路径算法的核心组成部分 
为了便于讲解：首先声明的是我的顶点是a,b,c,d,e,f,g,h其对应的编号分别为1，2，3，4，5，6，7，8.



void dijkstra(int startPos,int distance[],int path[],Graph *g)
{
    int mindis,nextNode,*mark;
    int i=0,j=0;
    mark=(int *)malloc(g->numVertexes*sizeof(int));
    for(i=0;i<g->numVertexes;i++)   //先将与起始点有边连接的点的距离
                                    //初始化为其与初始点的权值
    {
        distance[i]=getWeight(startPos,i,g);
        mark[i]=0;
        if(i!=startPos&&distance[i]<MAX)
            path[i]=startPos;
        else
            path[i]=-1;
    }
    mark[startPos]=1;
    for(i=0;i<g->numVertexes;i++)
    {
        mindis=MAX;
        for(j=0;j<g->numVertexes;j++)//循环1
        {
            if(mark[j]==0&&distance[j]<mindis)
            {
                nextNode=j;
                mindis=distance[j];
            }
        }
        if(mindis==MAX)
            return ;
        mark[nextNode]=1;
        for(j=0;j<g->numVertexes;j++)//循环2
        {
            if(mark[j]==0&&getWeight(nextNode,j,g)<MAX&&getWeight(nextNode,j,g)+distance[nextNode]<distance[j])
            {
                distance[j]=distance[nextNode]+getWeight(nextNode,j,g);
                path[j]=nextNode;
            }
        }
    }
} 

接下来我就逐步执行算法了 
a是起始点其编号为0    mark[0]=1，在循环1中找到距离最小点为b， 
mark[1]=1. 
执行循环2，发现c与b是相连的（权值不是10000）并且点c没被访问过(即mark[2]=0),然后比较a点直接到c点和a->b->c的距离哪个小（由于a->c无权值故设为10000即无穷大），发现a->b->c的距离更小，于是distance[2]=distance[1]+weight(b,c)   (注意distance[1]是初始化为a,b边的权值的）

执行循环2  
发现d与b是相连的（权值不是10000）并且d没有被访问过，然后比较distance[3]与distance[2]+weight(b,d)大小关系发现distance[3]更小于是就不改变distance[3]的值

由于其他点不满足条件循环结束

执行循环1 
编号2满足条件即c点满足条件，mark[2]=1,被标记

执行循环2 
发现编号3没有被标记，但是distance[3]     <    a->b->c->d所以distance[3]的值不改变 
继续执行循环2 
发现编号4即e点没被标记，且distance[4]=MAX故将distance[4]更新为a->b->c->e

剩下的执行情况类似，就不一一赘述啦。
        
            $(function () {
                $(‘pre.prettyprint code‘).each(function () {
                    var lines = $(this).text().split(‘\n‘).length;
                    var $numbering = $(‘<ul/>‘).addClass(‘pre-numbering‘).hide();
                    $(this).addClass(‘has-numbering‘).parent().append($numbering);
                    for (i = 1; i <= lines; i++) {
                        $numbering.append($(‘<li/>‘).text(i));
                    };
                    $numbering.fadeIn(1700);
                });
            });

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！