最短路径算法代码（最短路径算法描述）

今天给各位分享最短路径算法代码的知识，其中也会对最短路径算法描述进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、严蔚敏的数据结构（C语言版）最短路径算法 代码段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思
• 2、最短路径算法 C语言
• 3、c语言数据结构 最短路径问题代码
• 4、求c语言最短路径算法
• 5、C++ 编一个求最短路径
• 6、java 最短路径算法 如何实现有向 任意两点的最短路径

严蔚敏的数据结构（C语言版）最短路径算法 代码段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思

二维数组P中保存的是v0到各个点的最短路径。在v行中，值为true的列连起来，就是v0到v的最短路径。因为v0到w点的最短路径是v0到v的最短路径在加上v,w，所以w列先复制所有的v列的值，然后在将p[w][w]=true。此时w行中所有值为true列，就是v0到w的最短路径

最短路径算法 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写给我。

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 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++ 编一个求最短路径

程序如下，稍加改动即可。

带权有向图的最短路径的求解

//带权有向图的最短路径的求解

#include stdio.h

#include stdlib.h

#define MAXV 50

#define INF 32767

typedef int InfoType;

//邻接矩阵存储方法

typedef struct

{

int no;

InfoType info;

} VertexType;

typedef struct

{

int edges[MAXV][MAXV];

int n,e;

VertexType vexs[MAXV];

} MGraph;

//狄克斯特拉算法

void Ppath(int path[],int i,int v)

{

int k;

k=path[i];

if(k==v) return;

Ppath(path,k,v);

printf("%d,",k);

}

void Dispath(int dist[],int path[],int s[],int n,int v)

{

int i;

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

{

if(i==v) continue;

if(s[i]==1)

{

printf("从%d到%d的最短路径长度为：%d\t路径为：",v,i,dist[i]);

printf("%d,",v);

Ppath(path,i,v);

printf("%d\n",i);

}

else printf("从%d到%d不存在路径\n",v,i);

}

}

void Dijkstra(MGraph g,int v)

{

int dist[MAXV],path[MAXV];

int s[MAXV];

int mindis,i,j,u;

for(i=0;ig.n;i++)

{

dist[i]=g.edges[v][i];

s[i]=0;

if(g.edges[v][i]INF) path[i]=v;

else path[i]=-1;

}

s[v]=1;path[v]=0;

for(i=0;ig.n;i++)

{

mindis=INF;

for(j=0;jg.n;j++)

{

if(s[j]==0dist[j]mindis)

{

u=j;

mindis=dist[j];

}

}

s[u]=1;

for(j=0;jg.n;j++)

{

if(s[j]==0)

{

if(g.edges[u][j]INFdist[u]+g.edges[u][j]dist[j])

{

dist[j]=dist[u]+g.edges[u][j];

path[j]=u;

}

}

}

}

Dispath(dist,path,s,g.n,v);

}

//弗洛伊德算法

void Ppath1(int path[][MAXV],int i,int j)

{

int k;

k=path[i][j];

if(k==-1) return;

Ppath1(path,i,k);

printf("%d,",k);

Ppath1(path,k,j);

}

void Dispath1(int A[][MAXV],int path[][MAXV],int n)

{

int i,j;

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

{

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

{

if(i==j) continue;

if(A[i][j]==INF)

{

if(i!=j) printf("从%d到%d不存在路径\n",i,j);

}

else

{

printf("从%d到%d的最短路径长度为：%d\t路径为：",i,j,A[i][j]);

printf("%d,",i);

Ppath1(path,i,j);

printf("%d\n",j);

}

}

}

}

void Floyd(MGraph g)

{

int A[MAXV][MAXV],path[MAXV][MAXV];

int i,j,k;

for(i=0;ig.n;i++)

{

for(j=0;jg.n;j++)

{

A[i][j]=g.edges[i][j];

path[i][j]=-1;

}

}

for(k=0;kg.n;k++)

{

for(i=0;ig.n;i++)

{

for(j=0;jg.n;j++)

{

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

{

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

path[i][j]=k;

}

}

}

}

Dispath1(A,path,g.n);

}

//主函数

int main()

{

int i,j,n;

MGraph g;

printf("请输入带权有向图的顶点个数：");//6

while(scanf("%d",n)!=EOF)

{

printf("请输入带权有向图的邻接矩阵：\n");

/*

0 5 32767 7 32767 32767

32767 0 4 32767 32767 32767

8 32767 0 32767 32767 9

32767 32767 5 0 32767 6

32767 32767 32767 5 0 32767

3 32767 32767 32767 1 0

*/

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

{

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

{

scanf("%d",g.edges[i][j]);

}

}

g.n=n;

printf("采用狄克斯特拉算法得到的最短路径为：\n");

for(i=0;in;i++) Dijkstra(g,i);printf("\n");

printf("采用弗洛伊德算法得到的最短路径为：\n");Floyd(g);

printf("\n请输入带权无向图的顶点个数：");

}

return 0;

}

java 最短路径算法 如何实现有向 任意两点的最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：

1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点

2.初始阶段，将初始节点放入close，其他所有节点放入open

3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：

Node对象用于封装节点信息，包括名字和子节点

[java] view plain copy

public class Node {

private String name;

private MapNode,Integer child=new HashMapNode,Integer();

public Node(String name){

this.name=name;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public MapNode, Integer getChild() {

return child;

}

public void setChild(MapNode, Integer child) {

this.child = child;

}

}

MapBuilder用于初始化数据源，返回图的起始节点

[java] view plain copy

public class MapBuilder {

public Node build(SetNode open, SetNode close){

Node nodeA=new Node("A");

Node nodeB=new Node("B");

Node nodeC=new Node("C");

Node nodeD=new Node("D");

Node nodeE=new Node("E");

Node nodeF=new Node("F");

Node nodeG=new Node("G");

Node nodeH=new Node("H");

nodeA.getChild().put(nodeB, 1);

nodeA.getChild().put(nodeC, 1);

nodeA.getChild().put(nodeD, 4);

nodeA.getChild().put(nodeG, 5);

nodeA.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeA, 1);

nodeB.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeH, 4);

nodeC.getChild().put(nodeA, 1);

nodeC.getChild().put(nodeG, 3);

nodeD.getChild().put(nodeA, 4);

nodeD.getChild().put(nodeE, 1);

nodeE.getChild().put(nodeD, 1);

nodeE.getChild().put(nodeF, 1);

nodeF.getChild().put(nodeE, 1);

nodeF.getChild().put(nodeB, 2);

nodeF.getChild().put(nodeA, 2);

nodeG.getChild().put(nodeC, 3);

nodeG.getChild().put(nodeA, 5);

nodeG.getChild().put(nodeH, 1);

nodeH.getChild().put(nodeB, 4);

nodeH.getChild().put(nodeG, 1);

open.add(nodeB);

open.add(nodeC);

open.add(nodeD);

open.add(nodeE);

open.add(nodeF);

open.add(nodeG);

open.add(nodeH);

close.add(nodeA);

return nodeA;

}

}

图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径

[java] view plain copy

public class Dijkstra {

SetNode open=new HashSetNode();

SetNode close=new HashSetNode();

MapString,Integer path=new HashMapString,Integer();//封装路径距离

MapString,String pathInfo=new HashMapString,String();//封装路径信息

public Node init(){

//初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUE

path.put("B", 1);

pathInfo.put("B", "A-B");

path.put("C", 1);

pathInfo.put("C", "A-C");

path.put("D", 4);

pathInfo.put("D", "A-D");

path.put("E", Integer.MAX_VALUE);

pathInfo.put("E", "A");

path.put("F", 2);

pathInfo.put("F", "A-F");

path.put("G", 5);

pathInfo.put("G", "A-G");

path.put("H", Integer.MAX_VALUE);

pathInfo.put("H", "A");

//将初始节点放入close,其他节点放入open

Node start=new MapBuilder().build(open,close);

return start;

}

public void computePath(Node start){

Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close

if(nearest==null){

return;

}

close.add(nearest);

open.remove(nearest);

MapNode,Integer childs=nearest.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){//如果子节点在open中

Integer newCompute=path.get(nearest.getName())+childs.get(child);

if(path.get(child.getName())newCompute){//之前设置的距离大于新计算出来的距离

path.put(child.getName(), newCompute);

pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"-"+child.getName());

}

}

}

computePath(start);//重复执行自己,确保所有子节点被遍历

computePath(nearest);//向外一层层递归,直至所有顶点被遍历

}

public void printPathInfo(){

SetMap.EntryString, String pathInfos=pathInfo.entrySet();

for(Map.EntryString, String pathInfo:pathInfos){

System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());

}

}

/**

* 获取与node最近的子节点

*/

private Node getShortestPath(Node node){

Node res=null;

int minDis=Integer.MAX_VALUE;

MapNode,Integer childs=node.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){

int distance=childs.get(child);

if(distanceminDis){

minDis=distance;

res=child;

}

}

}

return res;

}

}

Main用于测试Dijkstra对象

[java] view plain copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

}

关于最短路径算法代码和最短路径算法描述的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。