最短路径算法c代码（最短路径算法c语言代码）

本篇文章给大家谈谈最短路径算法c代码，以及最短路径算法c语言代码对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、c语言数据结构 最短路径问题代码
• 2、最短路径算法 C语言
• 3、求floyd最短路径算法，c语言代码；
• 4、最短路径算法 Dijkstra 用C语言编出来
• 5、求c语言最短路径算法

c语言数据结构 最短路径问题代码

直接看代码：

#include stdlib.h

#define MAXVEX 10

typedef struct graph{

    int n,e;//顶点数、边数

    char vexs[MAXVEX];//顶点数组

    int arcs[MAXVEX][MAXVEX];//邻接矩阵

    int kind;//类型：0有向图；1无向图；2有向网；3无向网

} MGraph;

void PrintPath(MGraph G,int *p,int i){

    if(p[i]=0){

        PrintPath(G,p,p[i]);//先输出前驱顶点

    }

    printf("%c",G.vexs[i]);//输出本顶点

}

void Dijkstra(MGraph G, int v){

    //用Dijkstra算法求有向网G中序号为v的顶点到

    //其余各顶点的最短路径

    int *s,*d,*p,i,j,k,min;

    if(v0||v=G.n){//顶点编号参数错误

        printf("Dijkstra parameter ERROR! v0 Or v=%d",G.n);

        return;

    }

    s=(int *)malloc(sizeof(int)*G.n);

    d=(int *)malloc(sizeof(int)*G.n);

    p=(int *)malloc(sizeof(int)*G.n);

    for(i=0;iG.n;i++){ //初始化辅助数组，置0

        s[i]=0;d[i]=G.arcs[v][i];

        if(d[i]!=0)p[i]=v; //v是vi的直接前驱

        else p[i]=-1; //-1表示无直接前驱

    }

    s[v]=1;d[v]=0; //确定源点自身的最短路径长度

    printf("Dijkstra: (The shortest path from %c:)\n",G.vexs[v]);

    for(i=0;iG.n-1;i++){

        //确定v到其余n-1个顶点的最短路径

        min=32767;k=-1;

        for(j=0;jG.n;j++){

            //找出路径长度最小的顶点k

            if(!s[j]d[j]!=0d[j]min){

                k=j; min=d[k];

            }

        }

        if(k0){//有未能到达的顶点，把它们输出

            for(j=0;jG.n;++j){

                if(j==v)continue;

                if(s[j]==0){

                    printf("%c-%c: No path.\n",G.vexs[v],G.vexs[j]);

                }

            }

            free(s); free(d); free(p);

            return; //已完成或出现不连通的顶点

        }

        s[k]=1;

        printf("%c-%c: d=%-5d, p=",G.vexs[v],G.vexs[k],d[k]);

        PrintPath(G,p,k);//输出v到i的路径（正序）

        printf("\n");

        for(j=0;jG.n;j++){

            //更新其余顶点的最短路径及前驱

            if(!s[j]G.arcs[k][j]!=0(d[j]==0||d[j]d[k]+G.arcs[k][j])){

                d[j]=d[k]+G.arcs[k][j]; p[j]=k;

            }

        }

    }

    free(s); free(d); free(p);

}

这是单源的最短路径算法。

最短路径算法 C语言

#include stdio.h

#define MAXNODE 108

int path[MAXNODE + 1][MAXNODE + 1] = {0};

int main(void)

{

  FILE *fpr, *fpw;

  int va, vb, i, j, k;

  fpr = fopen("in.txt", "r"); /* 读取的文件名称in.txt */

  fpw = fopen("out.txt", "w"); /* path的数据在out.txt中展现 */

  while (fscanf(fpr, "%d%d", va, vb) != EOF)

    path[va][vb] = path[vb][va] = 1;

  for (k = 1; k = MAXNODE; ++k) {

    for (i = 1; i = MAXNODE; ++i) {

      for (j = 1; j = MAXNODE; ++j) {

        if (!path[i][k] || !path[k][j])

          continue;

        if (!path[i][j])

          path[i][j] = path[i][k] + path[k][j];

        else if (path[i][j]  path[i][k] + path[k][j])

          path[i][j] = path[i][k] + path[k][j];

      }

    } 

  }

  for (i = 1; i = MAXNODE; ++i) {

    for (j = 1; j = MAXNODE; ++j) {

      if (i == j)

        fprintf(fpw, "%-10d", 0);

      else if (path[i][j])

        fprintf(fpw, "%-10d", path[i][j]);    

      else 

        fprintf(fpw, "%-10d", -1);  

    }

    fprintf(fpw, "\n");

  }

  return 0;

}

注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！

这是之前的答案的错误之处。

-1表示不通。

具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。

求floyd最短路径算法，c语言代码；

就是一个三重循环，核心代码就这几行

for(k=0;kn;k++)

{

for(i=0;in;i++)

for(j=0;jn;j++)

if(A[i][j](A[i][k]+A[k][j]))

{

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

}

}

最短路径算法 Dijkstra 用C语言编出来

#include"iostream.h"

#include"stdlib.h"

#define MAXPOINT 3//定义最大的顶点数目

#define limit 32767 //设置没有路径的权代替无穷大

struct record{ //没个顶点的数据结构设置为一个数组队列

int number; //顶点号

int flag; //标志是否从队列中被选过如果为1表示选过为0表示未选

int allpath; //从源点到这个点的当前最短距离（权最小）

}path[MAXPOINT+1];

int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵

void main()

{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;

//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾

//N 表示待输入的源点号码 minnumber 表示选中的点的号码

int min=32768; //设置一个初始值

for(i=1;i=MAXPOINT;i++)

for(j=1;j=MAXPOINT;j++)

{cout"请输入从第"i"点到第"j"点的路径长度(权)如果没有路径的话请输入'32767' "endl;

cincost[i][j]; //初始化所有点之间的（权）路径值

}

//cout"请输入源点号"endl; //输入一个起点

//cinN;

for(N=MAXPOINT;N=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径

{ for(i=front;i=rear;i++) //初始化每个点的信息

{if(i==N)

path[i].allpath=0;

else

path[i].allpath=limit;

path[i].flag=0;

path[i].number=i;

}

while(rear=1) //控制循环次数

{for(temp=front;temp=MAXPOINT;temp++)

{ if(path[temp].allpathminpath[temp].flag==0)//选出一个具有最值

//的点

{ minnumber=path[temp].number;

min=path[temp].allpath ;

}

}

min=32768;

path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

for(i=1;i=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径

{if((i!=minnumber)(path[minnumber].allpath+cost[minnumber][i]path[i].allpath))

path[i].allpath=path[minnumber].allpath+cost[minnumber][i];

}

rear--;//次数减1

}

rear=MAXPOINT; //恢复数组以便于下一点的循环

for(j=1;j=MAXPOINT;j++)

{ cout"第"N"点到第"j"点的最短路径长度（权）为";

coutpath[j].allpath endl;

}

}

}

//这个程序可以求出任意一对顶点之间的最短路径，不过这种算法效率还不是很高，还有其他算法待续

求c语言最短路径算法

#include iostream

using namespace std;

const int maxnum = 100;

const int maxint = 999999;

// 各数组都从下标1开始

int dist[maxnum];     // 表示当前点到源点的最短路径长度

int prev[maxnum];     // 记录当前点的前一个结点

int c[maxnum][maxnum];   // 记录图的两点间路径长度

int n, line;             // 图的结点数和路径数

// n -- n nodes

// v -- the source node

// dist[] -- the distance from the ith node to the source node

// prev[] -- the previous node of the ith node

// c[][] -- every two nodes' distance

void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])

{

    bool s[maxnum];    // 判断是否已存入该点到S集合中

    for(int i=1; i=n; ++i)

    {

        dist[i] = c[v][i];

        s[i] = 0;     // 初始都未用过该点

        if(dist[i] == maxint)

            prev[i] = 0;

        else

            prev[i] = v;

    }

    dist[v] = 0;

    s[v] = 1;

    // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中

    // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度

         // 注意是从第二个节点开始，第一个为源点

    for(int i=2; i=n; ++i)

    {

        int tmp = maxint;

        int u = v;

        // 找出当前未使用的点j的dist[j]最小值

        for(int j=1; j=n; ++j)

            if((!s[j]) dist[j]tmp)

            {

                u = j;              // u保存当前邻接点中距离最小的点的号码

                tmp = dist[j];

            }

        s[u] = 1;    // 表示u点已存入S集合中

        // 更新dist

        for(int j=1; j=n; ++j)

            if((!s[j]) c[u][j]maxint)

            {

                int newdist = dist[u] + c[u][j];

                if(newdist dist[j])

                {

                    dist[j] = newdist;

                    prev[j] = u;

                }

            }

    }

}

// 查找从源点v到终点u的路径，并输出

void searchPath(int *prev,int v, int u)

{

    int que[maxnum];

    int tot = 1;

    que[tot] = u;

    tot++;

    int tmp = prev[u];

    while(tmp != v)

    {

        que[tot] = tmp;

        tot++;

        tmp = prev[tmp];

    }

    que[tot] = v;

    for(int i=tot; i=1; --i)

        if(i != 1)

            cout que[i] " - ";

        else

            cout que[i] endl;

}

int main()

{

    freopen("input.txt", "r", stdin);

    // 各数组都从下标1开始

    // 输入结点数

    cin n;

    // 输入路径数

    cin line;

    int p, q, len;          // 输入p, q两点及其路径长度

    // 初始化c[][]为maxint

    for(int i=1; i=n; ++i)

        for(int j=1; j=n; ++j)

            c[i][j] = maxint;

    for(int i=1; i=line; ++i) 

    {

        cin p q len;

        if(len c[p][q])       // 有重边

        {

            c[p][q] = len;      // p指向q

            c[q][p] = len;      // q指向p，这样表示无向图

        }

    }

    for(int i=1; i=n; ++i)

        dist[i] = maxint;

    for(int i=1; i=n; ++i)

    {

        for(int j=1; j=n; ++j)

            printf("%8d", c[i][j]);

        printf("\n");

    }

    Dijkstra(n, 1, dist, prev, c);

    // 最短路径长度

    cout "源点到最后一个顶点的最短路径长度: " dist[n] endl;

    // 路径

    cout "源点到最后一个顶点的路径为: ";

    searchPath(prev, 1, n);

}

最短路径算法c代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最短路径算法c语言代码、最短路径算法c代码的信息别忘了在本站进行查找喔。