最短路径算法

1、Dijkstra算法

目的是求解固定起点分别到其余各点的最短路径

步骤如下：

1. 准备工作：构建二位矩阵edge,edge[i][j]存储i->j的权重，如果i==j则edge[i][j]=0,如果i和j不是直达的，则edge[i][j]=MAX_INT
2. 构建数组dis[],其中dis[i]表示其实点start->i之间的权重，不断更新，得到最小的权重
3. 选取离start最近的直达点，（注，非直达的点一定会经过中间的跳变点，间接到达，首先考虑的一定是经过离start最近的点进行跳变）
4. 判断dis[i]与dis[离start最近的点index]+edge[离start最近的点index][i]的大小，更新dis[i]
5. 重复3-4(注意标记，防止重复计算)

#include 
     
      using namespace std;const int max_int = ~(1<<31);const int min_int = (1<<31);int main(){    int n,m,s;//n is the number of nodes, m is the number of edges and s is the start node.    int t1,t2,t3;//t1 is the start node, t2 is the end node and t3 is the weight between t1 and t2    cout<<"Please input the number of node(n), edges(m) and start node(s):"<
      
       >n>>m>>s;    int edge[n+1][n+1];//Store the edges for the n nodes    int dis[n+1], is_visited[n+1];// dis[k] store the min distance between s and k,\                                     is_visited store the status of the node(whether it is visited or not)    //Init the edge[][] with the max_int    for(int i=1; i<=n; i++){        for(int j = 1; j <= n; j++)            if(i==j) edge[i][j] = 0;            else edge[i][j] = max_int;    }    //Input the Edge data    cout<<"Please input the edge data: t1(start node), t2(end node), t3(weight)"<
       
        >t1>>t2>>t3;        edge[t1][t2] = t3;    }    /*     * Init the is_visited[] with 0     * Init the dis[]     */    for(int i=1; i<=n; i++){        is_visited[i] = 0;        dis[i] = edge[s][i];    }    is_visited[s] = 1;    //The Dijkstra algorithm    for(int i=1; i<=n; i++){        int u; // Store the min value index in dis[] which is not visited        int min = max_int; // Store the min value in dis[] which is not visited        for(int j=1; j<=n; j++){            if(is_visited[j]==0 && dis[j]
        
         dis[u]+edge[u][k]){                    dis[k] = dis[u] + edge[u][k];                    cout<
         <<" "<
          
           <<" "<
           
            <
           
          
        
       
      
     

 

2、Floyd算法

目的是求解任意两点的最短路径，核心思想是经过任意数量的节点进行中转，检查路径是否为最短

for(k=1;k<=n;k++)//经过k进行中转        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)                if(e[i][j]>e[i][k]+e[k][j])                     e[i][j]=e[i][k]+e[k][j];