search
HomeBackend DevelopmentC++How to use Dijkstra's algorithm in C++

How to use Dijkstra's algorithm in C++

Sep 19, 2023 pm 04:03 PM
c++ dijkstra algorithm use

How to use Dijkstras algorithm in C++

How to use Dijkstra's algorithm in C?

Dijkstra's algorithm is a greedy algorithm used to find the shortest path between two vertices in a weighted directed graph. Its core idea is to gradually expand the shortest path by continuously updating the shortest distance from the starting vertex to other vertices.

The following will introduce how to use C to implement Dijkstra's algorithm and give specific code examples.

Implementing Dijkstra's algorithm requires the following steps:

Step 1: Initialization.

First, we need to initialize some data structures, including the starting vertex start, the shortest distance array dist and the access status array visited. The starting vertex start specifies the starting point of the shortest path, the shortest distance array dist is used to record the current shortest distance from the starting vertex to other vertices, and the access status array visited is used to mark whether the vertex has been visited.

Step 2: Initialize the shortest distance array.

Initialize the shortest distance from the starting vertex to other vertices to infinity, and initialize the shortest distance from the starting vertex to itself to 0. Also marks the starting vertex as visited.

Step 3: Update the shortest distance array.

For all vertices adjacent to the starting vertex, if a shorter path can be found through the starting vertex, update the shortest distance array. The specific update method is to add the distance from the starting vertex to the current vertex plus the weight of the edge from the starting vertex to the current vertex, and compare it with the original shortest distance from the current vertex.

Step 4: Select the next nearest vertex.

Select the vertex closest to the starting vertex from the unvisited vertices as the next vertex to be visited.

Step 5: Repeat steps 3 and 4.

Repeat steps 3 and 4 until all vertices have been visited. Finally, what is stored in the shortest distance array dist is the shortest distance from the starting vertex to each vertex.

The following is a code example that uses C to implement Dijkstra's algorithm:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离:" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为:" << shortestDist[i] << endl;
    }

    return 0;
}

In the above code, we represent a weighted directed graph through a two-dimensional matrix. Each element in the matrix Element represents the weight of the edge between two vertices. Finally, the shortest distance from the starting vertex to each vertex is output.

The above is the detailed content of How to use Dijkstra's algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
C# vs. C   Performance: Benchmarking and ConsiderationsC# vs. C Performance: Benchmarking and ConsiderationsApr 25, 2025 am 12:25 AM

The performance differences between C# and C are mainly reflected in execution speed and resource management: 1) C usually performs better in numerical calculations and string operations because it is closer to hardware and has no additional overhead such as garbage collection; 2) C# is more concise in multi-threaded programming, but its performance is slightly inferior to C; 3) Which language to choose should be determined based on project requirements and team technology stack.

C  : Is It Dying or Simply Evolving?C : Is It Dying or Simply Evolving?Apr 24, 2025 am 12:13 AM

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C   in the Modern World: Applications and IndustriesC in the Modern World: Applications and IndustriesApr 23, 2025 am 12:10 AM

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

C   XML Libraries: Comparing and Contrasting OptionsC XML Libraries: Comparing and Contrasting OptionsApr 22, 2025 am 12:05 AM

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C   and XML: Exploring the Relationship and SupportC and XML: Exploring the Relationship and SupportApr 21, 2025 am 12:02 AM

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

C# vs. C  : Understanding the Key Differences and SimilaritiesC# vs. C : Understanding the Key Differences and SimilaritiesApr 20, 2025 am 12:03 AM

The main differences between C# and C are syntax, performance and application scenarios. 1) The C# syntax is more concise, supports garbage collection, and is suitable for .NET framework development. 2) C has higher performance and requires manual memory management, which is often used in system programming and game development.

C# vs. C  : History, Evolution, and Future ProspectsC# vs. C : History, Evolution, and Future ProspectsApr 19, 2025 am 12:07 AM

The history and evolution of C# and C are unique, and the future prospects are also different. 1.C was invented by BjarneStroustrup in 1983 to introduce object-oriented programming into the C language. Its evolution process includes multiple standardizations, such as C 11 introducing auto keywords and lambda expressions, C 20 introducing concepts and coroutines, and will focus on performance and system-level programming in the future. 2.C# was released by Microsoft in 2000. Combining the advantages of C and Java, its evolution focuses on simplicity and productivity. For example, C#2.0 introduced generics and C#5.0 introduced asynchronous programming, which will focus on developers' productivity and cloud computing in the future.

C# vs. C  : Learning Curves and Developer ExperienceC# vs. C : Learning Curves and Developer ExperienceApr 18, 2025 am 12:13 AM

There are significant differences in the learning curves of C# and C and developer experience. 1) The learning curve of C# is relatively flat and is suitable for rapid development and enterprise-level applications. 2) The learning curve of C is steep and is suitable for high-performance and low-level control scenarios.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)