dijkstra.txt

dijkstra算法

/*
最短路径
边松弛：测试沿着一条边，是否得到通向目标顶点的一条新的最短路径。
路径松弛：测试通过一个已知节点，是否可以得到一条连通其他两个已知顶点的新的最短路径。
性质：
如果顶点x是在从s到t的最短路径上，则该路径包含一条从s到x的最短路径，接着是一条从x到t的最短路径。
*/
//dijkstra算法
//以顶点到起始顶点的距离远近为顺序，在spt上添加顶点。
#include <stdlib.h>
#include <stdio.h>
typedef struct 
{
 int v;
 int w;
 double wt;
}Edge;
typedef struct graph* Graph;
struct graph { int v; int e;double **adj;};



Edge EDGE(int v,int w,double wt)
{
 Edge temp;
 temp.v=v;
 temp.w=w;
 temp.wt=wt;
 return temp;
 
}
double **matrixdouble(int r,int c,double val)
{
    int i,j;
    double **t=(double **)malloc(r*sizeof(double *));
    for(i=0;i<r;i++)
        t[i]=(double *)malloc(c*sizeof(double));
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
            t[i][j]=val;
    return t;
}



Graph init(int v)
{
    Graph g = (Graph)malloc(sizeof *g);
    g->v=v;
    g->e=0;
    g->adj=matrixdouble(v,v,1024);
    return g;
}
void insert(Graph g,Edge e)
{
    int v=e.v;
    int w=e.w;
    if(g->adj[v][w]==1024)
        g->e++;
    g->adj[v][w]=e.wt;
    //g->adj[w][v]=e.wt;
}
void show(Graph g)
{
    int i,j;
    printf("%d vetices, %d edges\n",g->v,g->e);
    for(i=0;i<g->v;i++)
    {
        printf("%2d:",i);
        for(j=0;j<g->v;j++)
            if(g->adj[i][j]!=-1)
                printf("%2d%5d",j,(int)g->adj[i][j]);
    printf("\n");
    }
}/*
 自己实现
 选择一个顶点作为源顶点
 利用权重数组初始化为源顶点到其他顶点的权重
 然后访问边，并更新权重数组，同时记录顶点连接数组
 */
void dijkstra(Graph g)
{
 int st[1024];
 double wt[1024];
 for(int i=0;i<g->v;i++)
 {
  st[i]=-1;
  wt[i]=g->adj[0][i];
 }
 //st[0]=;
 int n=0;
 
 for(int w=1;w<g->v;w++)
  for(int j=0;j<g->v;j++)
   
   {
   
    if(g->adj[n][w]+g->adj[w][j]<wt[j])//g->adj[n][j])
    {
     wt[j]=g->adj[n][w]+g->adj[w][j];
     st[j]=w;
    }
   }



 for(int m=0;m<g->v;m++)
 {
  int temp=st[m];
  printf("%d---",m);
 
   while(temp!=-1)
   {



    printf("%d---",temp);
    temp=st[temp];



   }
   if(temp==-1)
   printf("0");
  



  printf("\n");
 }



}
main()
{
 Graph g=init(5);
    insert(g,EDGE(0,1,10));
    //insert(g,EDGE(1,2,4));
  insert(g,EDGE(2,1,4));
    insert(g,EDGE(1,3,34));
    insert(g,EDGE(1,4,21));
    insert(g,EDGE(0,2,3));
    insert(g,EDGE(2,4,4));
 insert(g,EDGE(0,4,1));
 show(g);
 dijkstra(g);
 show(g);
 printf("\n");
 //show(g);
}