Dijkstra单元最短路径算法

朴灿烈づ我的快乐病毒、 2022-08-13 14:56 261阅读 0赞

**\#include<iostream>  
\#include<stack>  
using namespace std;  
\#define MAX   999999  
\#define M 100  
\#define N 100  
  
  
typedef struct node  
\{   
    int matrix\[M\]\[N\];  
    int n;    //定点数  
    int v;  //边数  
\}Graph;  
  
  
  
  
void Dijkstra(Graph g,int \*dist,int \*path,int v0)//v0是源定点  
\{  
    int i,j;  
    int \*visited=(int \*)malloc(sizeof(int)\*g.n);  
    path\[v0\]=v0;  
    dist\[v0\]=0;  
    for(i=0;i<g.n;i++)  
   \{  
       if(g.matrix\[v0\]\[i\]>0&&v0!=i)  
       \{  
            dist\[i\]=g.matrix\[v0\]\[i\];  
            path\[i\]=v0;  
        \}  
       else  
       \{  
            dist\[i\]=MAX;  
            path\[i\]=-1;  
        \}  
        visited\[i\]=0;  
         
    \}  
    visited\[v0\]=1;  
    for(i=0;i<g.n;i++)  
    \{  
  int k=0;  
       int min=MAX;  
       for(j=0;j<g.n;j++)  
       \{  
            if(min>dist\[j\]&&!visited\[j\])  
            \{  
                  min=dist\[j\];  
                  k=j;  
             \}  
       \}  
       visited\[k\]=1;  
        
  
  
       //更新  
       for(j=0;j<g.n;j++)  
       \{  
           if(dist\[j\]>dist\[k\]+g.matrix\[k\]\[j\]&&g.matrix\[k\]\[j\]>0&&!visited\[j\])  
           \{  
                   dist\[j\]=dist\[k\]+g.matrix\[k\]\[j\];  
                   path\[j\]=k;  
            \}  
       \}  
    \}  
  
  
  
  
\}  
  
  
  
  
void showPath(int \*path,int v,int v0)  
\{  
      stack<int>s;  
      int u=v;  
      while(v!=v0)  
      \{  
           s.push(v);  
          v=path\[v\];  
       \}  
       s.push(v);  
      while(!s.empty())  
      \{  
           cout<<s.top()<<' ';  
           s.pop();  
      \}  
\}  
  
  
int main()  
\{  
   int n,e,i,j;  
   int s,t,w;  
   int v0;  
   Graph  g;  
   cin>>n>>e;  
   int \*dist=(int \*)malloc(sizeof(int)\*n);  
   int \*path=(int \*)malloc(sizeof(int)\*n);  
   for(i=0;i<M;i++)  
   \{  
      for(j=0;j<N;j++)  
      \{  
          g.matrix\[M\]\[N\]=0;  
      \}  
   \}  
     
   g.n=n;  
   g.v=e;  
   for(i=0;i<e;i++)  
  \{  
      cin>>s>>t>>w;  
      g.matrix\[s\]\[t\]=w;  
   \}  
   cin>>v0;  
   Dijkstra(g,dist,path,v0);  
   for(i=0;i<n;i++)  
   \{  
      if(i!=v0)  
      \{  
         showPath(path,i,v0);  
         cout<<dist\[i\]<<endl;  
      \}  
   \}  
   system("pause");  
   return  0;  
    
\}**