最短路算法标程算法源代码.txt

最短路算法：基于遗传算法的一种最短路的MATLAB程序。

//..............................................................//
//      边权为正值的单源最短路 dijkstra  邻接矩阵               //
//         author:   sunmoonstar_love                           //
//..............................................................//

#include <stdio.h>
int const inf = 2140000000;
int const nV = 6; // 最大顶点个数
int graph[nV+1][nV+1]; // 图的邻接矩阵的表示
int dist[nV+1];  //存放从顶点0到其它个节点的最短路径的长度
int path[nV+1]; //存放在最短路径上该顶点的前一顶点的顶点号
int s[nV+1];    //集合表示顶点是否已经在最短路径中

inline void dijkstra(const int &n, const int &v)
{// graph是具有 n 个节点的带权有向图，由邻接矩阵graph[][]表示 从 0 开始 边权

为正值
 // dijkstra算法建立一个数组 dist， 0<=i<n, 是当前求到的从顶点 v 到 顶点 j 

的最短路径的长度
 // 同时用数组 path， 0<=i<n, 存放求到的最短路径
    int i,j,min,u,w;
    for(i=0; i<n; i++)
        dist = inf;
    dist[v] = 0;  //顶点 v 加入集合 S
    for(i=0; i<n; i++)
    {
        min = inf;
        u = v;
        for(j=0; j<n; j++)   // 搜索当前不在集合 S 中的具有最短路径的顶点 u
           if(!s[j] && dist[j]<min)
           {
               u = j;
               min = dist[j];
           }
        s = 1;
        for(w=0; w<n; w++)  //  修改现有的最短路
            if(!s[w] && graph[w]<inf && dist + graph[w]<dist[w])
            {
                path[w] = u;
                dist[w] = dist + graph[w];
            }                 
    }           
}    
///////////////////////////////////////////////////////////////////
//...............................................................//
//                                                               //
//           floyd-warshall 所有顶点间的最短路径                 //
//           适用:   允许有带负权的边，但是不允许有带负权的回路  //
//           author:   sunmoonstar_love                          //
//...............................................................//

//    Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，   //
//可以正确处理有向图（Directed Graph）或负权(negtive cost)的     //
//最短路径问题。Floyd-Warshall算法的时间复杂度为O(N3)。          //
//    其中Di,j表示由点i到点j的代价(cost)，当Di,j为 ∞表示两点    //
//之间没有任何连接（Disconnected）。                             //     

int const inf = 2147483647;
int const nV = 6;

int graph[nV+1][nV+1]; 
//graph是一个具有 n 个顶点的图的邻接矩阵

int shortpath[nV+1][nV+1];
//存所有顶点间的最短路，为了不破坏 graph[][]，而存在

int path[nV+1][nV+1]; 
// 存相应路径上顶点 j 的前一顶点

inline void floyd(const int &n)
{// 从 0 开始
    int i,j,k;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)   // 初始化
        {
            shortpath[j] = graph[j];  
            if(i!=j && shortpath[j]<inf)
                path[j] = i;             //有路径
            else
                path[j] = -1;             // 无路径
        }
    for(k=0; k<n; k++)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                if(shortpath[k]+shortpath[k][j]<shortpath[j])
                {
                    shortpath[j] = shortpath[k]+shortpath[k][j];
                    path[j] = path[k][j];//缩短路径长度，经过 k 到 j ？
                }       
}