dijkstra.txt

给定一个（无向）图G

实验目的：
       给定一个（无向）图G，及G中的两点s、t，确定一条从s到t的最短路径。
实验要求：
       输入图G的顶点数n。接下来的n行描述这一个图形，采用邻接表方式，其中的第i行有n个数，依次表示第i个顶点与第1、2、3、…、n个顶点的路径长。假如两个顶点间无边相连，用一个大数maxint（如65535）表示。再在下面的一行上给出两个整数i、j表示要求最短距离的两个顶点i和顶点j。
       输出两个顶点i和顶点j的最短距离，同时给出最短路径上的顶点序列。
       注意：每行上的两个相邻数间用一个空格隔开。
实验结果：
输入
4
0 2 65535 4
2 0 3 65535
65535 3 0 2
4 65535 2 0
1 3

输出
The least distance from l to 3 is 5.
The path is 1-> 2-> 3

程序代码：



#include<iostream>

using namespace std;
void Dijkstra(int n,int v,int dist[],int prev[],int **c)
{
    int maxint = 65535;
    bool *s = new bool[n];
    for (int i = 1; i <= n; i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = true;
    for (int i = 1; i < n; i++)
    {
        int temp = maxint;
        int u = v;
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = true;
        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;
                }
            }
        }
    }
}
void main()
{
    int n,v,u;
    int q = 0;
    cin>>n;
    int *way = new int[n + 1];
    int **c = new int *[n + 1];
    for (int i = 1; i <= n; i++)
    {
        c[i] = new int[n + 1];
    }
    for (int j = 1; j <= n; j++)
    {
        for (int t = 1; t <= n; t++)
        {
            cin>>c[j][t];
        }
    }
    int *dist = new int [n];
    int *prev = new int [n];
    cin>>v>>u;
    Dijkstra(n, v, dist, prev, c);
    cout<<"最短路径从"<<v<<" -> "<<u<<" 的距离是:"<<dist[u]<<endl;
    int w = u;
    while (w != v)
    {
        q++;
        way[q] = prev[w];
        w = prev[w];
    }
    cout<<"路径为：";
    for (int j = q; j >= 1; j--)
    {
        cout<<way[j]<<" ->";
    }
    cout<<u<<endl;
}



程序分析：
       a[i][j]记边（i,j）的权，数组dist[u]记从源v到顶点u所对应的最短特殊路径长度
       算法描述如下：
S1:初始化，S, T,对每个yS，{dist[y]=a[v][y],prev[y]=nil}
S2:若S=V，则输出dist,prev,结束
S3：uV\S中有最小dist值的点，SS{u}
S4：对u的每个相邻顶点x，调整dist[x]：即
若dist[x]>dist[u]+a[u][x],则{dist[x]=dist[u]+a[u][x]，prev[x]=u},转S2

       对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。

实验体会：
这个是经典贪谈心选择算法，与图论的结合更加加深了它的思维深度。画出一个表格之后，才得以理解。然后用书上的结构试验了一下，发觉一开始没有成功。是因为书上的有几个错误，在maxint等上面。修改好后，创建了一个2维动态数组，之后非常顺利。