最短路径算法

最短路径算法求助
要用Dijkstra算法，怎样把最终的 最短路径都经过 哪些点 也输出出来呀？

比如：最终节点v1到节点v3的最短路径是9，通过的路径是v1 -> v2 -> v3，v2怎么在程序中保存啊？

v1,v2 ... v6之间的邻接关系为：

C/C++ code

    v1        v2        v3        v4        v5        v6v1    INFINITY,    5,        INFINITY,    7,        INFINITY,    INFINITY,v2     INFINITY,    INFINITY,    4,        INFINITY,    INFINITY,    INFINITY,v3    8,        INFINITY,    INFINITY,    INFINITY,    INFINITY,    9,v4    INFINITY,    INFINITY,    5,        INFINITY,    INFINITY,    6,v5    INFINITY,    INFINITY,    INFINITY,    5,        INFINITY,    INFINITY,v6    3        INFINITY,    INFINITY,    INFINITY,    1,        INFINITY

先定义个结构体(老师给的伪代码)

C/C++ code

struct{            VertexTypevexs[MAX_VERTEX_NUM];  //顶点向量            int  arcs[][];                   //邻接矩阵            Int  vexnum,arcnum;              //图的当前顶点数和弧数        }MGraph;

然后写出函数

C/C++ code

void shortestpath (MGraph g,int v,pathmatrix &p,shortpathtable &d)

来得到功能：输出每个节点v(v1,v2 ... v6)到其他节点的最短路径，并写出最短路径中经过的节点。

我目前只知道怎样求出最短的路径是多长，但怎么求出其所经过的节点呢？



[解决办法]
定义一个数组来存放你所经过的路径，你每次更新最短路径的时候将节点存储进来。
[解决办法]
楼上正解 我这有个以前做过的题目 用Dijkstra算法 输出经过结点的 代码LZ要不
[解决办法]
你可以使用一个栈来保存路径 

探讨

引用:

定义一个数组来存放你所经过的路径，你每次更新最短路径的时候将节点存储进来。



每次更新都要保存吗？
能不能只保存最后的路径？

[解决办法]
你可以参考下，当时训练写的，虽然没有保存所经过的路径，但按照上几楼的说法，可以修改下

C/C++ code

#include <iostream>using namespace std; const int maxint = 32767;const int maxnode = 101;int dis[maxnode];int c[maxnode][maxnode];int prev[maxnode];int n, line;void dijkstra(int n, int v, int *prev, int dis[maxnode], int c[maxnode][maxnode]);void searchPath(int *prev,int v, int u);void main(){    cin >> n;    cin >> line;    int p, q, len;    for (int i = 1; i <= n; ++i)    {        for (int j = 1; j <= n; ++j)        {            c[i][j] = maxint;        }    }    for (i = 1; i <= line; ++i)    {        cin >> p >> q >> len;        if (len < maxint)        {            c[p][q] = len;            c[q][p] = len;        }    }    for (i = 1; i <= n; ++i)    {        dis[i] = maxint;    }    dijkstra(n, 1, prev, dis, c);    cout << dis[n] << endl;    searchPath(prev, 1, n);}void dijkstra(int n, int v, int *prev, int dis[maxnode], int c[maxnode][maxnode]){    bool s[maxint];    for (int i = 1; i <= n; ++i)    {        s[i] = 0;        dis[i] = c[v][i];        if (dis[i] < maxint)        {            prev[i] = v;        }        else        {            prev[i] = 0;        }    }        s[v] = 1;    dis[v] = 0;    for (i = 2; i <= n; ++i)    {        int temp = maxint;        int u;        for (int j = 1; j <= n; ++j)        {            if (!s[j] && dis[j] < temp)            {                u = j;                temp = dis[j];            }        }        s[u] = 1;        for (j = 1; j <= n; ++j)        {            int newdis = dis[u] +c[u][j];            if (newdis < dis[j])            {                dis[j] = newdis;                prev[j] = u;            }        }    }}void searchPath(int *prev,int v, int u){    int que[maxnode];    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;} 
  

 

查看更多 下一篇