//最短路径

/*



dijkstra




Dijkstra(迪杰斯特拉)算法的核心思想是贪心策略+动态规划

http://www.programgo.com/article/4721147659/

Dijkstra算法能得出最短路径的最优解，但是效率低

*/

/* 用邻接矩阵表示的图的Dijkstra算法的源程序*/

#include <iostream>

using namespace std;

#define MAXVEX 100

#define MAX 1e+8

typedef char VexType;

typedef float AdjType;

typedef struct

{

    int n;                            //图的顶点个数

  //  VexType vexs[MAXVEX];            //顶点

    AdjType arcs[MAXVEX][MAXVEX];   //边

}GraphMatrix;

typedef struct {

  //  VexType vertex;           //顶点信息

    AdjType length;       // 最短路径长度

    int prevex;          // 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前驱顶点

}Path;

Path dist[];          // n为图中顶点个数

void dijkstra(GraphMatrix graph, Path dist[])

{

    int i,j,minvex;

    AdjType min; // 初始化，此时集合U中只有顶点v0

    dist[].length = ;    dist[].prevex = ;

    graph.arcs[][] = ;   // 表示顶点v0在集合U中

    for(i = ; i < graph.n; i++)

    {  // 初始化集合V-U中顶点的距离值

        dist[i].length=graph.arcs[][i];

        if (dist[i].length != MAX)

            dist[i].prevex=;

        else  dist[i].prevex= -;

    }

    for(i = ; i < graph.n; i++)

    {

        min=MAX;    minvex=;

        for (j = ; j < graph.n; j++) //在V-U中选出距离值最小顶点

            if( graph.arcs[j][j] ==  && dist[j].length < min )

            {

                min=dist[j].length;  minvex=j;

            }

        if(minvex == ) break;    // 从v0没有路径可以通往集合V-U中的顶点

        graph.arcs[minvex][minvex] = ;    // 集合V-U中路径最小的顶点为minvex

        for (j = ; j < graph.n; j++)

        {

            // 调整集合V-U中的顶点的最短路径

            if(graph.arcs[j][j] == )  continue;

            if(dist[j].length > dist[minvex].length + graph.arcs[minvex][j]) {

                dist[j].length = dist[minvex].length + graph.arcs[minvex][j];

                dist[j].prevex = minvex;

            }

        }

    }

}

GraphMatrix graph;

void initgraph(){

    int i,j;

    graph.n=;

    for (i = ; i < graph.n; i++)

        for (j = ; j < graph.n; j++)

            graph.arcs[i][j] = (i == j ?  : MAX);

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

    graph.arcs[][] = ;

}

int main(){

    int i;

    initgraph();

    dijkstra(graph, dist);

    for (i = ; i < graph.n; i++)

        printf("(%.0f %d)\t", dist[i].length,dist[i].prevex);

    system("pause");

    return ;

}

//============================================================================

//Floyed: 往点中间插入其他点，动态：s[i][k] + s[k][j] < s[i][j]

//test case

/

//============================================================================

#include <iostream>

using namespace std;

int main()

{

    int n,m,i,j,k,l,r;

    cout<<"输入结点数和边数\n";

    cin>>n>>m;

    int**s=new int*[n];//确定的是行数

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

    {

        s[i]=new int[n];//确定的是列数

    }

    //初始化，将自己与自己的距离置为0，任意两点距离置为99999

    for(i=;i<n;i++){

        for(j=;j<n;j++)

        {  if(i==j)  s[i][j]=;

        s[i][j]=;

        }

    }

    //Input:

    cout<<"输入结点和两个结点的权值\n";

    for(k=;k<m;k++)

    {

        cin>>i>>j;

        cin>>s[i][j];

    }

    for (k=; k<n; k++)

        for (i=; i<n; i++)

            for (j=; j<n; j++)

                if (s[i][k] + s[k][j] < s[i][j])

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

    cout<<"输入起始和终止结点"<<endl;

    cin>>l>>r;

    cout<<s[l][r]<<endl;

    system("pause");

    return ;

}

*

*/