21xrx.com
2024-12-31 20:23:14 Tuesday
登录
文章检索 我的文章 写文章
C++实现邻接矩阵下的Dijkstra算法
2023-07-11 05:41:42 深夜i     --     --
C++ 邻接矩阵 Dijkstra算法 图 最短路径

Dijkstra算法是一种解决单源最短路径问题的贪心算法，它可以在有向图或无向图中找到一个节点到其他所有节点的最短路径。在这个算法中，我们需要用到邻接矩阵来表示图的结构，使用C++语言实现Dijkstra算法可以方便地处理一些大型图的问题。

邻接矩阵是一种二维数组，其中每个元素描述了图中的边的关系。邻接矩阵可以很容易地描述出图中的所有边，这使它成为了处理图问题的一种常见数据结构。邻接矩阵可以用来表示带权重的图，也可以用来描述无向图或者有向图。

在实现Dijkstra算法时，我们首先需要标记起点到其他节点的距离为无限大，然后再将起点到自己的距离标记为0。接下来，我们需要对起点进行遍历，并更新其他节点的距离。每当我们发现一条较小的路径时，我们需要将其更新为当前已经发现的最小路径。遍历所有节点后，我们可以获得起点到其他所有节点的最短路径。

下面是使用C++语言实现Dijkstra算法的示例代码：

#include

#include

using namespace std;

const int MAX = 100;

int graph[MAX][MAX];

int dist[MAX];

bool visited[MAX];

void dijkstra(int nodes, int start){

  for(int i=0; i

    dist[i] = INT_MAX; //将所有距离初始化为无限大

    visited[i] = false; //将所有节点都视为未被访问

  }

  dist[start] = 0; //将起点到自己的距离设为0

  for(int i=0; i

    int closest = INT_MAX;

    int u;

    for(int j=0; j

      if(!visited[j] && dist[j] <= closest){

        closest = dist[j];

        u = j;

      }

    }

    visited[u] = true; //标记该节点已被访问

    for(int v=0; v

      if(!visited[v] && graph[u][v] != 0 && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v]){

        dist[v] = dist[u]+graph[u][v]; //更新距离

      }

    }

  }

  //输出结果

  cout << "节点\t最短路径" << endl;

  for(int i=0; i

    cout << i << "\t" << dist[i] << endl;

  }

}

int main(){

  int nodes, edges;

  cout << "请输入图的节点数和边数：";

  cin >> nodes >> edges;

  //初始化邻接矩阵

  for(int i=0; i

    for(int j=0; j

      graph[i][j] = 0;

    }

  }

  //读取边的关系和权重

  for(int i=0; i

    int u, v, w;

    cout << "请输入边的两个节点和权重：";

    cin >> u >> v >> w;

    graph[u][v] = w;

    //如果是无向图，则需要将对应位置的权重也进行更新

    graph[v][u] = w;

  }

  int start;

  cout << "请输入起点：";

  cin >> start;

  dijkstra(nodes, start);

  return 0;

}

在本示例中，我们使用了一个graph数组来表示邻接矩阵，它的大小为MAX*MAX，其中MAX的值可以根据实际问题进行调整。在运行程序时，用户需要输入图的节点数和边数，以及边的两个节点和对应的权重。程序会输出起点到其他节点的最短路径。

总之，使用C++实现邻接矩阵下的Dijkstra算法可以轻松地解决单源最短路径问题。虽然在处理大型图中会有一定的复杂度，但相对于其他的算法，Dijkstra算法具有良好的运行效率和可读性，这使其成为了解决图问题的一个常用算法。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复